Yet Another Number Sequence—

Yet Another Number Sequence——[矩阵快速幂]

Description

　　Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation:

F₁ = 1, F₂ = 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 ≥ 1).

In this problem, your task is to calculate the following sum: A₁(k) + A₂(k) + ... + A_n(k). The answer can be very large, so print it modulo 1000000007(10⁹ + 7).

Input

　　The first line contains two space-separated integers n, k(1 ≤ n ≤ 10¹⁷; 1 ≤ k ≤ 40).

Output

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

Sample Input

Input

1 1

Output

Input

4 1

Output

Input

5 2

Output

Input

7 4

Output

73825

解题思路：
　　这是一道矩阵快速幂求多项式的应用，思路很清晰：找到各个量之间的递推关系，用矩阵求幂转移状态。问题的关键在于推导A（n，k），sumA（n），
F（n）之间的关系。过程如下：
　　1.令 U（n＋1，k）＝F（n＋1）＊（n＋1）^k；
　　　　　V（n＋1，k）＝F（n）＊（n＋1）^k；
　　　　Sum（n）＝∑［i＝1～n］A（i，k）；
　　2.利用二项式定理将（1+i）^n展开；
　　则 U（n＋1，k）＝∑［i＝0～k］C（i，k）＊F（n）＊（n）^i＋∑［i＝0～k］C（i，k）＊F（n－1）＊（n）^i
　　　　　　　　　　　　＝∑［i＝0～k］C（i，k）＊U（n，i）＋∑［i＝0～k］C（i，k）＊V（n，i）；
　　同理 V（n＋1，k）＝∑［i＝0～k］C（i，k）＊U（n，i）；
　　Sum（n）＝Sum（n－1）＋U（n，k）；
　　
　　3.状态转移用矩阵向量表示：

sum（n-1）		sum(n)
U(n,k)		U(n+1,k)
...		...
U(n,0)	=>	U(n+1,0)
V(n,k)		V(n+1,k)
...		...
V(n,0)		V(n+1,0)







代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <time.h>
 5 #include <assert.h>
 6 #define time_ printf("time : %f
",double(clock())/CLOCKS_PER_SEC)
 7 using namespace std;
 8 #define maxk 40
 9 #define MOD 1000000007
10 #define mod_(x) (x%MOD)
11 
12 typedef long long LL;
13 LL n;
14 int k;
15 
16 struct Matrix{
17     int row,col;
18     int m[2*maxk+5][2*maxk+5];
19     Matrix(int r=83,int c=83){
20         row=r;
21         col=c;
22         memset(m, 0, sizeof m);
23     }
24     void operator=(const Matrix& m2){
25         memcpy(m, m2.m, sizeof m);
26     }
27 };
28 Matrix operator*(const Matrix& a,const Matrix& b){
29     Matrix c(a.row,b.col);
30     for(int i=0;i<c.row;i++)
31         for(int j=0;j<c.col;j++){
32             for(int p=0;p<a.col;p++){
33                 c.m[i][j]=(c.m[i][j]+LL(a.m[i][p])*b.m[p][j])%MOD;
34                 //assert(c.m[i][j]>=0);
35             }
36         }
37     return c;
38 }
39 Matrix C;
40 void set_C(){
41     for(int i=k;i>=0;i--)
42         for(int j=k;j>=i;j--){
43             if(j==k||j==i)
44                 C.m[i][j]=1;
45             else
46                 C.m[i][j]=(C.m[i+1][j]+C.m[i+1][j+1])%MOD;
47             }
48 }
49 void cpy_C(Matrix& a,int pi,int pj){
50     int len=k+1;
51     for(int i=0;i<len;i++)
52         for(int j=0;j<len;j++)
53             a.m[pi+i][pj+j]=C.m[i][j];
54 }
55 void set_M(Matrix& a){
56     a.m[0][0]=1,a.m[0][1]=1;
57     cpy_C(a, 1, 1);
58     cpy_C(a, k+2, 1);
59     cpy_C(a, 1, k+2);
60 }
61 Matrix pow_mod(Matrix& a,LL n){
62     if(n==1) return a;
63     Matrix temp=pow_mod(a, n/2);
64     temp=temp*temp;
65     if(n%2){
66         temp=temp*a;
67     }
68     return temp;
69 }
70 int pow_2(int n){
71     if(n==0) return 1;
72     int temp=pow_2(n/2)%MOD;
73     temp=int((LL(temp)*temp)%MOD);
74     if(n%2)
75         temp=(temp*2)%MOD;
76     return temp;
77 }
78 int main(int argc, const char * argv[]) {
79     while(scanf("%lld%d",&n,&k)==2){
80         if(n==1){
81             printf("%d
",1);
82             continue;
83         }
84         set_C();
85         Matrix I(2*k+3,2*k+3);
86         set_M(I);
87         Matrix A(2*k+3,1);
88         A.m[0][0]=1;
89         for(int i=1;i<k+2;i++)
90             A.m[i][0]=pow_2(k+1-i+1);
91         for(int i=k+2;i<2*k+3;i++)
92             A.m[i][0]=pow_2(2*k+2-i);
93         Matrix temp=pow_mod(I, n-1);
94         A=temp*A;
95         printf("%d
",A.m[0][0]);
96         //time_;
97     }
98     return 0;
99 }