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

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로 나눈 나머지를 출력한다.

예제 입력 1

1 1

예제 출력 1

1

예제 입력 2

4 1

예제 출력 2

34

예제 입력 3

5 2

예제 출력 3

316

예제 입력 4

7 4

예제 출력 4

73825