시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 27 7 6 40.000%

문제

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

F1 = 1, F2 = 2, Fi = Fi-1 + Fi-2 (i > 2).

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

Ai(k) = Fi × ik (i ≥ 1).

n과 k가 주어졌을 때, A1(k) + A2(k) + ... + An(k)를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 A1(k) + A2(k) + ... + An(k)를 109 + 7로 나눈 나머지를 출력한다.

예제 입력

1 1

예제 출력

1

예제 입력 2

4 1

예제 출력 2

34

예제 입력 3

5 2

예제 출력 3

316

예제 입력 4

7 4

예제 출력 4

73825

힌트

출처