#P392C. Yet Another Number Sequence
Yet Another Number Sequence
Description
Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation:
We'll define a new number sequence Ai(k) by the formula:
In this problem, your task is to calculate the following sum: A1(k) + A2(k) + ... + An(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).
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 Ai(k) modulo 1000000007 (109 + 7).
Samples
1 1
1
4 1
34
5 2
316
7 4
73825