RWY造函数

题目描述:

众所周知,RWY是一个特别爱搞怪的小盆友。
听闻要举办新生欢乐杯比赛,RWY特别开(fa)(dian)
于是他造了一个函数f(x)=xx mod (x+1),并给出一个正整数n,想请你求出f(1)+ f(2)+ f(3)++f(n)的值。
由于答案比较大,请你输出答案对10000取模后的结果。

输入格式:

输入共一行为一个正整数n

输出格式:

输出一行一个整数,表示[f(1)+ f(2)+ f(3)++f(n)]mod 10000的值。

样例输入:

5

样例输出:

11

提示:

对于30%的数据,1<=n<=1000
对于70%的数据,1<=n<=106
对于100%的数据,1<=n<=109
时间限制: 1000ms
空间限制: 128MB

来源: 2016新生欢乐赛1