CF392C.Yet Another Number Sequence

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 ≥ 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 (109 + 7).

众所周知斐波那契数列是什么。该数列可通过如下递推关系定义：

$F_1 = 1,\ F_2 = 2,\ F_i = F_{i-1} + F_{i-2}\ (i > 2)$。

我们通过以下公式定义一个新的数列 $A_i(k)$：

$A_i(k) = F_i \times i^k\ (i \geq 1)$。

本题中，你需要计算如下和式：$A_1(k) + A_2(k) + \dots + A_n(k)$。答案可能非常大，因此请输出其对 $1000000007$（即 $10^9 + 7$）取模的结果。

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

第一行包含两个以空格分隔的整数 $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 (109 + 7).

输出一个整数——序列 $A_i(k)$ 的前 $n$ 项之和对 $1000000007$（即 $10^9 + 7$）取模的结果。