Description

幼儿园的老师总是喜欢和孩子们玩游戏，他们经常会让孩子们围成一圈，然后开始玩报数游戏，从其中的一个孩子开始，1，2，3，4，5......一个个报下去，如果一个孩子报错了，那么那个孩子就要表演节目给大家看哦。

今天，学校里新来了一个妙妙老师，她突发奇想，想考考大家，于是她也出了一个游戏，游戏规则是这样的：

1.n个孩子们站成一排，编号分别是1，2，3，4......n

2.孩子们手上都拿着一张纸，若这个孩子的编号是i，那么纸上的数字是i(i+1)(i+2)

3.如果孩子只说出自己的纸上的数字， 那么是不难的，可是， 孩子要说出，前面所有孩子和自己纸上的和.

例如，大仙的编号是2，那么她要说123+234 = 30，其实很好懂， 对不对。。。

哎， 这可为难了小朋友啊，那么难的题目， 而且， 那么多的小朋友， 该怎么办呢，你来帮帮他们好吗？

Input

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

Output

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

Sample

Input

1
2
3

Output

6
30
90

Hint

daodao友情提示 　　　　 1^2+2^2+...+n^2=( n(n+1)(2n+1) ) /6 　　　　 1^3+2^3+...+n^3=( n^2 (n+1)^2 )/4

Source: 闪电