502008 - 多项式乘法

【题目描述】多项式乘法(mult)

已知n的值,你需要做一种多项式的展开,该种多项式的格式为:(x+a1)(x+a2)(x+a3)…(x+an-1)(x+an)。 当n=2时,展开式为:x2+x(a1+a2)+a1a2。 当n=3时,展开式为:x3+x2(a1+a2+a3)+x(a1a2)+a1a3+a2a3+a1a2a3。 最上面的数字为的是让你看清展开式的总长度。每一个字符(包括“x”,“a”,“(”,“)”,“+”),每一个指数的每一个数字,每一个下标的每一个数字长度都为1。如n=3时,总长度为40。

Input

输入包含一个整数n(0<n≤1000000000)。

Output

若展开式的总长度为t,则输出t mod 10000的值。

Examples

Input

3

Output

40
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题