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).

输入描述:

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

输出描述:

Print a single integer — the sum of the first n elements of the sequence Ai(k) modulo 1000000007(109 + 7).