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


def fibonacci(i):
    if i == 1:
        return 1
    elif i == 2:
        return 2
    else:
        return fibonacci(i-1) + fibonacci(i-2)


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

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

    sum = 0

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

    print(sum)
    sum = sum % 10**9
    print(sum)
