题目描述

定义复数 $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

1000

1752541

1000000

636408476

数据范围与提示