← 返回题目列表

Codeforces · 392/C

C. 又一个数字序列

中文机器翻译题面 查看原题

每个人都知道斐波那契数列是什么。该序列可以通过递推关系来定义:

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