Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation: 

We'll define a new number sequence *A*<sub class="lower-index">*i*</sub>(*k*) by the formula: 

In this problem, your task is to calculate the following sum: *A*<sub class="lower-index">1</sub>(*k*) + *A*<sub class="lower-index">2</sub>(*k*) + ... + *A*<sub class="lower-index">*n*</sub>(*k*). The answer can be very large, so print it modulo 1000000007 (10<sup class="upper-index">9</sup> + 7).
The first line contains two space-separated integers *n*, *k* (1 ≤ *n* ≤ 10<sup class="upper-index">17</sup>; 1 ≤ *k* ≤ 40).

# coding: utf-8

# In[14]:


#Codeforces Round #230 (Div. 1)
#Problem C
n , k = input().split()
n = int(n)
k = int(k)
a = 1
b = 1
i = 1
sum = 0
while(n):
    #print(b)
    c = a + b 
    a = b 
    b = c
    #print(b,i)
    sum = sum + a * (i**k)
    i = i +1
    n = n - 1
print(sum%1000000007)

