题目描述

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

当$\red{n=2}$时,展开式为:$\red{x^2 +x(a_1 +a_2) +a_1a_2}$。

当$\red{n=3}$时,展开式为:$\red{x^3 +x^2(a_1 +a_2 +a_3)+x(a_1a_2 +a_1a_3 +a_2a_3)+a_1a_2a_3}$

每一个字符(包括"$\red{x}$"、"$\red{a}$"、"$\red{(}$"、"$\red{)}$"、"$\red{+}$"),每一个指数的每一个数字,每一个下标 的每一个数字长度都为$\red{1}$。如$\red{n=3}$时,总长度为$\red{40}$。

输入格式

输人文件包含一个整数$\red{n(0<n≤}$$\red{10^9)}$。

输出格式

输出文件若展开式的总长度为$\red{t,}$则输出$\red{t~mod~10000}$的值($\red{1}$除$\red{10000}$取余)。

样例

输入样例

3

输出样例

40