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$ $(10^{9} + 7)$.

Input

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

Output

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