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