题目描述
多项式相乘的展开是件相当繁琐的工作，DoubleRun快要烦死了。他把这个任务交给了你。为了简化，他只要你做一种多项式的展开，该种多项式的格式为：(x+a1)(x+a2)(x+a3)...(x+an-1)(x+an),n的值事先给你
当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
输入
包含一个整数n(0
输出
若展开式的总长度为t,则输出t mod 10000的值
样例输入
3
样例输出
40
来源/分类
组合数学