数论函数簇

【题目描述】

在数论上，算术函数（或称数论函数）指定义域为正整数、陪域为复数的函数，每个算术函数都可视为复数的序列。

最重要的算术函数是积性及加性函数。算术函数的最重要操作为狄利克雷卷积，对于算术函数集，以它为乘法，一般函数加法为加法，可以得到一个阿贝尔环。

对于特殊的数论函数往往有许多特殊的性质，我们研究一种经典函数F(n,a,b)(x)=(ax+b) mod n(0<a<n,0<=b<n)。数论函数R(n)为n为定值时F(n,a,b)(F(n,a,b)(x))=F(n,a,b)(x)的不同的a,b二元组个数。

输入N求Σ(1<=i<=N)R(i)

【输入格式】

输入一个正整数N

【输出格式】

输出和式的结果除以1005060097的余数

【样例输入】

6

【样例输出】

10

【提示】

数据范围和注释

对于20%的数据，N≤5000。

对于50%的数据，N≤10^6。

对于100%的数据，N≤10^11。

样例解释：10=0+1+1+1+1+6

【来源】

在此键入。