每个人都知道斐波那契数列是什么。该序列可以通过递推关系来定义:
F1 = 1,F2 = 2,Fi = Fi - 1 + Fi - 2 (i > 2)。
我们将通过以下公式定义一个新的数列 Ai(k):
Ai(k) = Fi × ik (i ≥ 1)。
在此问题中,您的任务是计算以下总和:A1(k) + A2(k) + ... + An(k)。答案可能非常大,因此打印它对 1000000007 (109 + 7) 取模。
输入
第一行包含两个空格分隔的整数 n, k (1 ≤ n ≤ 1017; 1 ≤ k ≤ 40)。
输出
打印单个整数 — 序列 Ai(k) 的前 n 个元素的总和以 1000000007 (109 + 7) 为模。
示例
输入 #1
1 1
输出 #1
1
输入 #2
4 1
输出 #2
34
输入 #3
5 2
输出 #3
316
输入#4
7 4
输出#4
73825