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

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

输入格式

一行一个整数 $n$。

输出格式

一行一个整数表示答案。

样例

样例输入 1

5

样例输出 1

35

样例输入 2

1000

样例输出 2

1752541

样例输入 3

1000000

样例输出 3

636408476

数据范围与提示

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