在跳蚤国，一位名叫跳蚤比克的贤者发现了一个奇妙的函数 $f(x)$，是一种「跳蚤魔力函数」。「跳蚤魔力函数」满足 $f(1)=1$ 且对于任意 $p,q$ 使得 $\gcd(p,q)=1$，都有 $f(pq)=f(p)f(q)$。此外，在质数 $p$ 的 $k$ 次幂处，它的点值恰好等于一个华丽的二次函数 $w(p^k)$。在跳蚤国的历史上，这个函数曾经被古老的智慧封存起来，直到跳蚤比克的发现。

在定都仪式的阅兵会上，跳蚤国的领导者们决定利用这个函数来增强国家的魔力。于是，在跳蚤国的红色广场上，一群跳蚤兵被精心地排列成了一个巨大的 $n\times n$ 矩阵。每一只跳蚤都蕴含着一定的魔力，而这个魔力的值取决于它所处的位置。更为具体地，第 $i$ 行第 $j$ 列的跳蚤拥有着 $f(ij)$ 的魔力。

跳蚤国王想要知道如何计算所有跳蚤产生的魔力值之和。但是一个一个数过去太慢了，所以跳蚤国王需要你的帮助。为了不为难你，你只需要求出答案对 $998244353$ 取模后的结果就行了。

输入格式

一行四个非负整数 $n,w_0,w_1,w_2$。其中 $w(x) = w_0+xw_1+x^2w_2$。

输出格式

一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例一

input

12 3 2 1

output

1239814

样例二 $\sim$ 样例五

见下发文件。

限制与约定

• Subtask 1（5 points）：保证 $n\le 10^3$。
• Subtask 2（25 points）：保证 $n\le 3\times 10^4$。
• Subtask 3（15 points）：保证 $n\le 10^6$。
• Subtask 4（25 points）：保证 $n\le 3 \times 10^7$。
• Subtask 5（10 points）：保证 $n\le 10^8$。
• Subtask 6（15 points）：保证 $n\le 3 \times 10^8$。
• Subtask 7（5 points）：无特殊限制。

对于所有数据，保证 $1 \le n\le 10^9$，$0\le w_0,w_1,w_2 < 998244353$。

时间限制：$\texttt{6s}$

空间限制：$\texttt{1024MB}$