Play game

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

幼儿园的老师总是喜欢和孩子们玩游戏,他们经常会让孩子们围成一圈,然后开始玩报数游戏,从其中的一个孩子开始,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

Hint

lcy

Source

2009 Multi-University Training Contest 16 -

提交代码