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

시간 제한2초메모리 제한512 MB

요약

F_1=1, F_2=2인 피보나치 수 F_i에 대해 F_i 곱하기 i^k를 i=1부터 n까지 더한 값을 구한다. n은 10^17까지 커질 수 있다.

문제

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

$F_1 = 1, \quad F_2 = 2, \quad F_i = F_{i-1} + F_{i-2} \quad (i > 2)$

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

$A_i(k) = F_i \times i^k \quad (i \ge 1)$

$n$ 과 $k$ 가 주어졌을 때 $A_1(k) + A_2(k) + \cdots + A_n(k)$ 를 구하는 프로그램을 작성하시오.

첫째 줄에 $n$ 과 $k$ 가 공백으로 구분되어 주어진다. ( $1 \le n \le 10^{17}$ , $1 \le k \le 40$ )

첫째 줄에 $A_1(k) + A_2(k) + \cdots + A_n(k)$ 를 $10^9 + 7$ 로 나눈 나머지를 출력한다.