Yet Another Number Sequence

题意翻译

# 题目描述 所有人都知道什么是斐波那契数列（相信洛谷的童鞋们都知道），他是由以下数列表示的： $F_1=1,F_2=2$ 通项公式：F[i]=F[i-1]+F[i-2] 我们要找到一个新数列$A_i(k)$，其通项公式是： $A_i(k)=F_i*i^k(i>=1)$ 我们找到了你，希望你求出这个算式的结果： # $A_1(k)+A_2(k)+...+A_n(k)$ 这个算式的结果会很大，所以要求你将结果对$10^9+7$取余。 # 输入输出格式 ## 输入 输入两个数$n,k(1<=n<=10^{17},1<=k<=40)$. ## 输出 输出仅一行，代表算式的结果（对$10^9+7$取余）。

题目描述

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&gt;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_{1}(k)+A_{2}(k)+...+A_{n}(k) $ . The answer can be very large, so print it modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

1 1

输出样例 #1

1

输入样例 #2

4 1

输出样例 #2

34

输入样例 #3

5 2

输出样例 #3

316

输入样例 #4

7 4

输出样例 #4

73825