多项式相乘

【题目描述】

多项式相乘的展开是一件相当烦琐的工作，FireDancer快要烦死了。他把这个任务交给了你。为了简化，他只要你做一种多项式的展开，该种格式为$(x+a_1)(x+a_2)(x+a_3)...(x+a_{n-1})(x+a_n)$。 当n=$2$时，展开式为$x^2+x(a_1+a_2)+a_1 a_2$。 当n=$3$时，展开式为$x^3+x^2(a_1+a_2+a_3)+x(a_1a_2+a_1a_3+a_2a_3)+a_1a_2a_3$。 每一个字符（包括“$x$”、“$a$”、“$($”、“$)$”、“$+$”），每一个指数的每一个数字，每一个下标的每一个数字长度都为$1$。如$n=3$时，总长度为$40$。

【输入】

一个整数$n$。

【输出】

若展开式的总长为$t$，则输出$t\bmod 10000$（$t$除$10000$取余）。

【输入样例】

3

【输出样例】

40

【提示】

【数据规模】 对于30%的数据，$n≤10$。 对于100%的数据，$n≤10^9$。