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).
from __future__ import print_function
import sys

if __name__ == "__main__":
    input = [int(x) for x in input().split()]

    n = input[0]
    k = input[1]

    sum = 0

    fib_a = 1
    fib_b = 1

    limit = 10**9

    for i in range(1, (n + 1), 1):
        Ai = fib_b * (i ** k)
        sum += (Ai % limit)

        fib_b += fib_a
        fib_a = fib_b - fib_a
    print(sum)
