问题描述

多项式相乘的展开是件相当烦琐的工作,DoubleRun快要烦死了。他把这个任务交给了你。为了简 化,他只要你做一种多项式的展开,该种多项式的格式为：$(x+a_1)(x+a_2)(x+a_3)…(x+a_{n-1}) (x+a_n),n$的值事先给你。

• 当n=2时,展开式为:$x_2 +x(a_1+a_2 )+a_1a_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 mod 10000的值（t除10000取余）。

样例

3

40

数据范围

$0<n≤10^9$

来源

• 信息学奥赛之数学一本通
• stong9070整理