多项式相乘的展开是件相当烦琐，DoubleRun快烦死了。他把这个任务交给了你。为了简化，他
只要你做一种多项式的展开，该种多项式的格式为：（x+a1）（x+a2）(x+a3)…(x+an-1)（x+an）,
n的值事先给你：
当n=2,展开式为：x^2+x(a1+a2)+a1a2;
当n=3，x^3+x^2(a1+a2+a3)+x(a1a2+a1a3+a2a3)+a1a2a2;
每一个字符（包括“x”,"a","(",")"、“+”），每一个指数的每一个数自，每一个下标的每一
个数字长度都为1，如n=3时，总长度为40.
输入格式
输入文件包含一个整数n（0<n≤10^9）
输出格式
输出文件若展开式的总长度为t，则输出t mod 10 000的值（t除10 000取余）
输入样例
3
输出样例
40