У Тимофея было очень много стажёров, целых N (0 ≤ N ≤ 106) человек. Каждый стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными — они сделали по одному коммиту.
Пусть Fi —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). Первые два стажёра сделали по одному коммиту: F0=F1=1. Для всех i ≥ 2 выполнено Fi=Fi-1+Fi-2.
Определите, сколько кода напишет следующий стажёр – найдите последние k цифр числа Fn.
Как найти k последних цифр
Чтобы вычислить k последних цифр некоторого числа x, достаточно взять остаток от его деления на число 10k. Эта операция обозначается как x mod 10k. Узнайте, как записывается операция взятия остатка по модулю в вашем языке программирования.
В первой строке записаны через пробел два целых числа n (0 ≤ n ≤ 106) и k (1 ≤ k ≤ 8).
Выведите единственное число – последние k цифр числа Fn. Если в искомом числе меньше k цифр, то выведите само число без ведущих нулей.
| Ввод | Вывод |
|---|---|
| 3 1 | 3 |
| Ввод | Вывод |
|---|---|
| 10 1 | 9 |