Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

C. Yet Another Number Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Input

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

Output

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

Examples
Input
1 1
Output
1
Input
4 1
Output
34
Input
5 2
Output
316
Input
7 4
Output
73825