F. Fibonacci Fever
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given $$$n$$$ and $$$k$$$ you're asked to compute

$$$$$$ \sum_{i = 1}^{n} f_{i}^{k} $$$$$$

where $$$f_{n}$$$ is the $$$n$$$-th fibonacci number. The $$$n$$$-th fibonacci number can be computed as:

$$$$$$ f_{1} = f_{2} = 1 $$$$$$ $$$$$$ f_{n} = f_{n - 1} + f_{n - 2}, \forall n \geq 3 $$$$$$

Since the answer could be large, print it modulo $$$10^{9} + 7$$$.

Input

The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$1 \leq k \leq 10^{5}$$$) — The limits of the sum and the exponent of all the terms.

Output

Print a single line — The value of the required sum modulo $$$10^{9} + 7$$$.

Examples
Input
1 10
Output
1
Input
5 10
Output
9825700
Input
10 1
Output
143
Input
2 1
Output
2
Input
3 1
Output
4
Input
4 1
Output
7