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+x(a1+a2)+a1a2。
当n=3时,展开式为:x3+x2(a1+a2+a3)+x(a1a2+a1a3+a2a3)+a1a2a3
每一个字符(包括“x”、“a”、“(”、“)”、“+”),每一个指数的每一个数字,每一个下标的每一个数字长度都为1。如n=3时,总长度为40。
输入
输入文件包含一个整数n(0<n≤109)。
输出
输出文件若展开式的总长度为t,则输出t mod 10000的值(t除10000取余)。
样例输入 复制
3
样例输出 复制
40