Fibonacci Fever#12483
Sign in

Fibonacci Fever

Hard

Given two integers and , compute the value:

\sum_{i=1}^{n} f_i^k,

where f_i is the -th Fibonacci number.

The Fibonacci sequence is defined as follows:

f_1 = f_2 = 1, \\ f_n = f_{n-1} + f_{n-2}, n \ge 3.

Since the answer can be very large, print it modulo 10^9 + 7.

Input

One line contains two integers and k~(1 \le n \le 10^{18}, 1 \le k \le 10^5) where:

  • is the number of terms in the sum,

  • is the exponent applied to each Fibonacci number.

Output

Print one integer — the value of the sum:

\sum_{i=1}^{n} f_i^k \mod (10^9 + 7)

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading