幼儿园的老师总是喜欢和孩子们玩游戏，他们经常会让孩子们围成一圈，然后开始玩报数游戏，从其中的一个孩子开始，1，2，3，4，5......一个个报下去，如果一个孩子报错了，那么那个孩子就要表演节目给大家看哦。 
今天，学校里新来了一个小明老师，她突发奇想，想考考大家，于是她也出了一个游戏，游戏规则是这样的： 
1.n个孩子们站成一排，编号分别是1，2，3，4......n 
2.孩子们手上都拿着一张纸，若这个孩子的编号是i，那么纸上的数字是i*(i+1)*(i+2) 
3.如果孩子只说出自己的纸上的数字， 那么是不难的，可是， 孩子要说出，前面所有孩子和自己纸上的和.例如，晶晶的编号是2，那么她要说1*2*3+2*3*4 = 30，其实很好懂， 对不对。。。 
哎， 这可为难了小朋友啊，那么难的题目， 而且， 那么多的小朋友， 该怎么办呢，你来帮帮他们好吗？ 

Input

输入孩子的编号n（1<=n<=10^100）

Output

孩子该报出来的数,最后 mod 9999

Sample Input

1
2
3

Sample Output

6
30
90

题解：把n(n+1)(n+2)展开，然后提出公因式来，最后从1*2*3这样的开始加到n(n+1)(n+2)就能发现有很多都能消去

最后会得到 答案等于n(n+1)(n+2)(n+3)/4

这些都不是重点，重点是学习一下取模的公式

最简单的

  • (a + b) % p = (a%p + b%p) %p
  • (a - b) % p = ((a%p - b%p) + p) %p
  • (a * b) % p = (a%p)*(b%p) %p

这些是紫书上的，然后还缺一个除法取模的公式

(a / b) % p = (a * inv(a) ) % p = (a % p * inv(a) % p) % p

推理详见，逆元求法详见 

其实这道题，肯定不会爆因为 b才4,当很大的时候就能用上这些公式了

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double INF = 1e20;
const double pi = acos (-1.0);
typedef long long int ll;
#define maxn 100000+5
int main(){
    string s;
    while(cin>>s){
        ll n=0;
        for(int i=0;i<s.size();i++){
            n=(n*10+s[i]-'0')%9999;
        }
        ll ans=n*(n+1)*(n+2)*(n+3)/4;
        printf("%lld\n",ans%9999);

    }
    return 0;
}