13716번 - 피보나치 수열처럼 보이지만...

피보나치 수열은 다음과 같이 정의된다.

F₁ = 1, F₂ = 2, F_i = F_i-1 + F_i-2 (i > 2).

A_i(k)는 다음과 같이 정의 된다.

A_i(k) = F_i × i^k (i ≥ 1).

n과 k가 주어졌을 때, A₁(k) + A₂(k) + ... + A_n(k)를 구하는 프로그램을 작성하시오.

첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 10¹⁷, 1 ≤ k ≤ 40)

첫째 줄에 A₁(k) + A₂(k) + ... + A_n(k)를 10⁹ + 7로 나눈 나머지를 출력한다.