У Тимофея было очень много стажёров, целых N (0 ≤ N ≤ 10⁶) человек. Каждый стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными — они сделали по одному коммиту.

Пусть F_i —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). Первые два стажёра сделали по одному коммиту: F₀=F₁=1. Для всех i ≥ 2 выполнено F_i=F_i-1+F_i-2.

Определите, сколько кода напишет следующий стажёр – найдите последние k цифр числа F_n.

Как найти k последних цифр

Чтобы вычислить k последних цифр некоторого числа x, достаточно взять остаток от его деления на число 10^k. Эта операция обозначается как x mod 10^k. Узнайте, как записывается операция взятия остатка по модулю в вашем языке программирования.

В первой строке записаны через пробел два целых числа n (0 ≤ n ≤ 10⁶) и k (1 ≤ k ≤ 8).

Выведите единственное число – последние k цифр числа F_n. Если в искомом числе меньше k цифр, то выведите само число без ведущих нулей.