CF1017F.The Neutral Zone

Notice: unusual memory limit!

After the war, destroyed cities in the neutral zone were restored. And children went back to school.

The war changed the world, as well as education. In those hard days, a new math concept was created.

As we all know, logarithm function can be described as: $$ \log(p_1^{a_1}p_2{a_2}...p_k^{a_2}) = a_1 \log p_1 + a_2 \log p_2 + ... + a_k \log p_k $$ Where $p_1^{a_1}p_2^{a_2}...p_k^{a_2}$ is the prime factorization of a integer. A problem is that the function uses itself in the definition. That is why it is hard to calculate.

So, the mathematicians from the neutral zone invented this: $$ \text{exlog}_f(p_1^{a_1}p_2{a_2}...p_k^{a_2}) = a_1 f(p_1) + a_2 f(p_2) + ... + a_k f(p_k) $$

Notice that $\text{exlog}_f(1)$ is always equal to $0$.

This concept for any function $f$ was too hard for children. So teachers told them that $f$ can only be a polynomial of degree no more than $3$ in daily uses (i.e., $f(x) = Ax^3+Bx^2+Cx+D$).

"Class is over! Don't forget to do your homework!" Here it is: $$ \sum_{i=1}^n \text{exlog}_f(i) $$

Help children to do their homework. Since the value can be very big, you need to find the answer modulo $2^{32}$.

注意：内存限制异常！

战争结束后，中立区被摧毁的城市得以重建，孩子们也重返校园。

战争改变了世界，也改变了教育。在那些艰难的日子里，一种新的数学概念应运而生。

众所周知，对数函数可表示为：

$$\log(p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}) = a_1 \log p_1 + a_2 \log p_2 + \dots + a_k \log p_k$$

其中 $p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$ 是某个正整数的质因数分解。问题在于该函数在其自身定义中又用到了自身，因此难以直接计算。

于是，中立区的数学家们提出了如下定义：

$$\text{exlog}_f(p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}) = a_1 f(p_1) + a_2 f(p_2) + \dots + a_k f(p_k)$$

注意：对任意函数 $f$，恒有 $\text{exlog}_f(1) = 0$。

然而，对于任意函数 $f$ 的这一概念对孩子们而言过于困难。因此老师们规定：在日常使用中，$f$ 只能是次数不超过 $3$ 的多项式（即 $f(x) = Ax^3 + Bx^2 + Cx + D$）。

“下课！别忘了完成家庭作业！”题目如下：

$$\sum_{i=1}^n \text{exlog}_f(i)$$

请帮助孩子们完成这项作业。由于结果可能非常大，你只需输出答案对 $2^{32}$ 取模的结果。

The only line contains five integers $n$, $A$, $B$, $C$, and $D$ ($1 \le n \le 3 \cdot 10^8$, $0 \le A,B,C,D \le 10^6$).

唯一的一行包含五个整数 $n$、$A$、$B$、$C$ 和 $D$（$1 \le n \le 3 \cdot 10^8$，$0 \le A,B,C,D \le 10^6$）。

Print the answer modulo $2^{32}$.

以 $2^{32}$ 为模输出答案。

In the first sample:

$\text{exlog}_f(1) = 0$

$\text{exlog}_f(2) = 2$

$\text{exlog}_f(3) = 3$

$\text{exlog}_f(4) = 2 + 2 = 4$

$\text{exlog}_f(5) = 5$

$\text{exlog}_f(6) = 2 + 3 = 5$

$\text{exlog}_f(7) = 7$

$\text{exlog}_f(8) = 2 + 2 + 2 = 6$

$\text{exlog}_f(9) = 3 + 3 = 6$

$\text{exlog}_f(10) = 2 + 5 = 7$

$\text{exlog}_f(11) = 11$

$\text{exlog}_f(12) = 2 + 2 + 3 = 7$

$ \sum_{i=1}^{12} \text{exlog}_f(i)=63 $

In the second sample:

$\text{exlog}_f(1) = 0$

$\text{exlog}_f(2) = (1 \times 2^3 + 2 \times 2^2 + 3 \times 2 + 4) = 26$

$\text{exlog}_f(3) = (1 \times 3^3 + 2 \times 3^2 + 3 \times 3 + 4) = 58$

$\text{exlog}_f(4) = 2 \times \text{exlog}_f(2) = 52$

$ \sum_{i=1}^4 \text{exlog}_f(i)=0+26+58+52=136 $

在第一个样例中：

$\text{exlog}_f(1) = 0$

$\text{exlog}_f(2) = 2$

$\text{exlog}_f(3) = 3$

$\text{exlog}_f(4) = 2 + 2 = 4$

$\text{exlog}_f(5) = 5$

$\text{exlog}_f(6) = 2 + 3 = 5$

$\text{exlog}_f(7) = 7$

$\text{exlog}_f(8) = 2 + 2 + 2 = 6$

$\text{exlog}_f(9) = 3 + 3 = 6$

$\text{exlog}_f(10) = 2 + 5 = 7$

$\text{exlog}_f(11) = 11$

$\text{exlog}_f(12) = 2 + 2 + 3 = 7$

$ \sum_{i=1}^{12} \text{exlog}_f(i)=63 $

在第二个样例中：

$\text{exlog}_f(1) = 0$

$\text{exlog}_f(2) = (1 \times 2^3 + 2 \times 2^2 + 3 \times 2 + 4) = 26$

$\text{exlog}_f(3) = (1 \times 3^3 + 2 \times 3^2 + 3 \times 3 + 4) = 58$

$\text{exlog}_f(4) = 2 \times \text{exlog}_f(2) = 52$

$ \sum_{i=1}^4 \text{exlog}_f(i)=0+26+58+52=136 $