题目描述

多项式相乘的展开是件相当繁琐的工作，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$，$0<n\le 10^9$。

输出格式

若展开式的总长度为 $t$，则输出 $t\mod 10^4$ 的值。

3

40