4933: 《信息学奥赛之数学一本通》第3章 组合数学 【例3.5-6】 多项式相乘

内存限制:64 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

多项式相乘的展开是件相当烦琐的工作,DoubleRun快要烦死了。他把这个任务交给了你。为了简化,他只要你做一种多项式的展开,该种多项式的格式为:
x+a1)(x+a2)(x+a3…(x+an-1)(x+an),n的值事先给你。
n=2时,展开式为:x2+xa1+a2+a1a2
n=3时,展开式为:x3+x2a1+a2+a3+xa1a2+a1a3+a2a3+a1a2a3
 
每一个字符(包括x”、“a”、“(”、“)”、“+”),每一个指数的每一个数字,每一个下标的每一个数字长度都为1。如n=3时,总长度为40



输入

输入文件包含一个整数n0<n109)。

输出

输出文件若展开式的总长度为t,则输出t mod 10000的值(t10000取余)。

样例输入 复制

3

样例输出 复制

40