注意:内存限制异常!
战后,中立区被摧毁的城市被恢复。孩子们回到了学校。
战争改变了世界,也改变了教育。在那段艰难的日子里,一个新的数学概念被创造出来。
众所周知,对数函数可以描述为: $$$$$$ \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 $$$