题目描述

多项式相乘的展开是一件相当烦琐的工作，FireDancer快要烦死了。他把这个任务交给了你。为了简化，他只要你做一种多项式的展开，该种格式为$(x+a_1)(x+a_2)(x+a_3)...(x+a_{n-1})(x+a_n)$。 当n=$2$时，展开式为$x^2+x(a_1+a_2)+a_1 a_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\bmod 10000$（$t$除$10000$取余）。

输入样例

3

输出样例

40

提示

【数据规模】 对于30%的数据，$n≤10$。 对于100%的数据，$n≤10^9$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。