| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 1006 | 314 | 199 | 34.729% |
피보나치 수열은 다음과 같이 정의된다.
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
4 1
34
5 2
316
7 4
73825