该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile6052.zip](file://AdditionalFile6052.zip?type=additional_file)

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

标签: 传统 | 时间限制: 3000 ms | 内存限制: 256 MiB |

题目描述

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

输入格式

一行一个整数 $n$。

输出格式

一行一个整数表示答案。

样例 1

输入

5

输出

35

样例 2

输入

1000

输出

1752541

样例 3

输入

1000000

输出

636408476

数据范围与提示