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取模。

【样例说明】 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