511007 - 特别拆分

【题目描述】特别拆分(lqp)

出题者定义F0=0,F1=1,Fn=Fn−1+Fn−2 (n>1),Fn就是斐波那契数列的第n项。接下来他考虑对整数进行特别拆分,即满足任意m>0,a1,a2,a3 …am>0,且a1+a2+a3+…+am=n的一个有序集合。特别拆分要求的不是拆分总数,而是对于每个拆分,出题者定义这个拆分的权值Fa1,Fa2 …Fam,他想知道对于所有的拆分,它们的权值之和是多少? 简单来说,就是求∑▒∏(i=1)^m▒F(a_i ) 。

输入

输入的第一行包含一个整数n(1≤n≤1010000)。

输出

输出一行一个整数表示答案。由于答案可能非常大,所以要对109 +7取模。

样例

输入

    3

输出

    5

提示

【样例说明】 F0=0,F1=1,F2=1,F3=2 对于n=3,有这样几种特别拆分: 3=1+1+1,权值是F1×F1×F1=1×1×1=1 3=1+2,权值是F1×F2=1×1=1 3=2+1,权值是F2×F1=1×1=1 3=3,权值是F3=2 所以答案是1+1+1+2=5

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题