多项式相乘的展开是一件相当烦琐的工作，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$。