#P392C. Yet Another Number Sequence
-
ID: 2906
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Yet Another Number Sequence
No submission language available for this problem.
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