Все знают, что такое ряд чисел Фибоначчи. Это последовательность, которую можно определить следующим рекуррентным соотношением:
Определим новую последовательность чисел Ai(k) следующей формулой:
В этой задаче вам требуется посчитать следующую сумму: A1(k) + A2(k) + ... + An(k). Ответ может быть очень большим, поэтому выведите его по модулю 1000000007 (109 + 7).
В первой строке записано два целых числа через пробел n, k (1 ≤ n ≤ 1017; 1 ≤ k ≤ 40).
Выведите единственное целое число — сумму первых n элементов последовательности Ai(k) по модулю 1000000007 (109 + 7).
1 1
1
4 1
34
5 2
316
7 4
73825
| Codeforces Round 230 (Div. 1) |
|---|
| Закончено |
