Обратите внимание на необычное ограничение по памяти!
После войны разрушенные города в нейтральной зоне были восстановлены и дети опять пошли в школу.
Война изменила мир, так же как и образование. В те сложные дни в математике было придумано новое понятие.
Мы все знаем, что функцию логарифма можно записать как: \(\) \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}\).
Выходные данные
Выведите ответ по модулю \(2^{32}\).
Примечание
В первом примере:
\(\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 \)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12 0 0 1 0
|
63
|
|
2
|
4 1 2 3 4
|
136
|