2888: 多项式相乘

    多项式相乘的展开是一件相当烦琐的工作，FireDancer快要烦死了。他把这个任务交给了你。为了简化，他只要你做一种多项式的展开，该种格式为(x+a1)(x+a2)(x+a3)…(x+an-1)(x+an),n的值事先给你。当n=2，展开式为x2+x(a1+a2)+a1a2；当n=3时，展开式为

（最上面的数字为的是让你看清展开式的总长度）。每一个字符（包括“x”、“a”、“（”、“）”、“+”），每一个指数的每一个数字，每一个下标的每一个数字长度都为1。如n=3时，总长度为40。

    一个整数n（0<n<=1,00 0,000,000）。

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

3

40