# Description

Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation:
$F_1 = 1,F_2 = 2,F_i = F_{i-1}+F_{i-2}(i>2)$
We'll define a new number sequence $A_i(k)$by the formula:
$A_i(k) = F_i * i^k(i \ge 1)$
In this problem, your task is to calculate the following sum:$A_1(k)+A_2(k)+\cdots+A_n(k)$.The answer can be very large, so print it modulo $1000000007$($10^9+7$).

# Input

The first line contains two space-separated integers $n$, $k$ (1 ≤ $n$ ≤ $10^{17}$; 1 ≤ $k$ ≤ 40).

# Output

Print a single integer — the sum of the first $n$ elements of the sequence $A_i(k)$ modulo $1000000007 (10^9 + 7).$

# 思路

$(n+1)^k = C(^0_k)*{n^0} + C(^1_k)*{n^1}+ \cdots + C(^k_k)*{n^k}$ $(n+1)^k = \displaystyle\sum_{i=0}^{k}(C(^i_k)*{n^i})$

\begin{align} g_1(n+1,k) &= fib(n+1)*(n+1)^k \\ &= (fib(n)+fib(n-1))*(n+1)^k \\ &= (fib(n)+fib(n-1))*(\displaystyle\sum_{i=0}^{k}{C(^i_k)*{n^i})} \\ &= \displaystyle\sum_{i=0}^{k}{C(^i_k)*(fib(n)*{n^i+fib(n-1)*{n^i})}} \\ &= \displaystyle\sum_{i=0}^{k}{C(^i_k)*(g_1(n,i)+g_2(n,i))} \\ g_2(n+1,k) &=fib(n)*(n+1)^k \\ &= fib(n)*(\displaystyle\sum_{i=0}^{k}{C(^i_k)*{n^i}}) \\ &= \displaystyle\sum_{i=0}^{k}{C(^i_k)*(fib(n)*{n^i})} \\ &= \displaystyle\sum_{i=0}^{k}{C(^i_k)*g_1(n,i)} \end{align} 根据式子我们可以得到转移矩阵。
$\begin{bmatrix}g_1(n+1,0)\\g_1(n+1,1)\\\vdots\\g_1(n+1,k)\\g_2(n+1,0)\\g_2(n+1,1)\\\vdots\\g_2(n+1,k)\\sum(n+1,k)\end{bmatrix} = \begin{bmatrix}C(^0_k)&C(^1_k)&\cdots&C(^k_k)&C(^0_k)&C(^1_k)&\cdots&C(^k_k)\\0&C(^1_k)&\cdots&C(^k_k)&0&C(^1_k)&\cdots&C(^k_k)\\\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&C(^k_k)&0&0&\cdots&C(^k_k)\\C(^0_k)&C(^1_k)&\cdots&C(^k_k)&0&0&\cdots&0\\0&C(^1_k)&\cdots&C(^k_k)&0&0&\cdots&0\\\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&C(^k_k)&0&0&\cdots&C(^k_k)\\0&0&\cdots&1&0&0&\cdots&1\end{bmatrix}*\begin{bmatrix}g_1(n,0)\\g_1(n,1)\\\vdots\\g_1(n,k)\\g_2(n,0)\\g_2(n,1)\\\vdots\\g_2(n,k)\\sum(n,k)\end{bmatrix}$ 然后我们使用矩阵快速幂，求出$sum(n,k)$就是最后的答案。

0%