#170. #6052. 「雅礼集训 2017 Day11」DIV

#6052. 「雅礼集训 2017 Day11」DIV

说明

定义复数 a+bi a + bi a+bi 为整数 k k k 的约数,当且仅当 a a a 和 b b b 为整数且存在整数 c c c 和 d d d 满足 (a+bi)(c+di)=k (a + bi)(c + di) = k (a+bi)(c+di)=k,给定 n n n,求出 1 1 1 到 n n n 的所有满足 a>0 a > 0 a>0 的约数 a+bi a + bi a+bi 的 a a a 的和。答案模 1004535809 1004535809 1004535809 输出。

输入格式

一行一个整数 n n n。

输出格式

一行一个整数表示答案。

样例

5
35

提示

测试点 n n n
1 ≤10 \leq 10 ≤10
2 ≤100 \leq 100 ≤100
3 ≤200 \leq 200 ≤200
4 ≤300 \leq 300 ≤300
5 ≤400 \leq 400 ≤400
6 ≤500 \leq 500 ≤500
7 ≤3000 \leq 3000 ≤3000
8 ≤5000 \leq 5000 ≤5000
9 ≤3×106 \leq 3 \times 10 ^ 6 ≤3×106
10 ≤5×106 \leq 5 \times 10 ^ 6 ≤5×106
11 ≤7×106 \leq 7 \times 10 ^ 6 ≤7×106
12 ≤107 \leq 10 ^ 7 ≤107
13 ≤3×108 \leq 3 \times 10 ^ 8 ≤3×108
14 ≤5×108 \leq 5 \times 10 ^ 8 ≤5×108
15 ≤7×108 \leq 7 \times 10 ^ 8 ≤7×108
16 ≤109 \leq 10 ^ 9 ≤109
17 ≤3×109 \leq 3 \times 10 ^ 9 ≤3×109
18 ≤5×109 \leq 5 \times 10 ^ 9 ≤5×109
19 ≤7×109 \leq 7 \times 10 ^ 9 ≤7×109
20 ≤1010 \leq 10 ^ {10} ≤1010