3735. 斐波那契数列数列

【题目描述】

记 $F(i)$ 表示斐波那契数列，其中 $F(1)=F(2)=1 ， F(i)=F(i-1)+F(i-2)$ 

记 $F^2(i)$ 表示 $F(i)$ 的前 $i$ 项和，$F^3(i)$ 表示 $F^2(i)$ 的前 $i$ 项和……

以此类推，$F^n(i)$ 表示 $F^{n-1}(i)$ 的前 $i$ 项和。

试求 $F^n(k)$ 的值模 $1e9+7$ 。

【输入格式】

两个正整数，$n,k$ 

【输出格式】

一个非负整数，$F^n(k)$ 的值模 $1e9+7$ 

【样例输入】

2 5

【样例输出】

12

【样例说明】

$F(i)=\{1,1,2,3,5,…\}$

$F^2(i)=\{1,2,4,7,12,…\}$

【数据规模与约定】

对于$40\%$数据，$2≤n,k≤10^{3}$

对于另$20\%$数据，$n=2$

对于另$10\%$数据，$n≤4$

对于$90\%$数据，$2≤n,k≤10^{6}$

对于$100\%$数据，$2≤n≤10^{6},1≤k≤10^{18}$

【提示】

$F(1)=F(2) ， F(3)=F(4)-F(2) ， F(5)=F(6)-F(4)……$

相加得：$F(1)+F(3)+F(5)+…+F(2n-1)=……$

【来源】

$rsr$