502008 - 多项式乘法

【题目描述】多项式乘法（mult）

已知n的值，你需要做一种多项式的展开，该种多项式的格式为：(x＋a1)(x＋a2)(x＋a3)…(x＋an-1)(x＋an)。 当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＜n≤1000000000)。

若展开式的总长度为t，则输出t mod 10000的值。