← 返回题目列表

Codeforces · 1017/F

F. 中立区

中文机器翻译题面 查看原题

注意:内存限制异常!

战后,中立区被摧毁的城市被恢复。孩子们回到了学校。

战争改变了世界,也改变了教育。在那段艰难的日子里,一个新的数学概念被创造出来。

众所周知,对数函数可以描述为: $$$$$$ \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 $$$$$$ 其中$$$p_1^{a_1}p_2^{a_2}...p_k^{a_2}$$$ 是整数的素因数分解。问题是该函数在定义中使用了自身。这就是为什么它很难计算。

所以,来自中立区的数学家发明了这个: $$$$$$ \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) $$$$$$

请注意 $$$\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}$$$ 求模答案。

输入

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

输出

打印以 $$$2^{32}$$$ 为模的答案。

示例

输入 #1

12 0 0 1 0

输出 #1

63

输入 #2

4 1 2 3 4

输出 #2

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 $$$