Фибоначчи по модулю

У Тимофея было очень много стажёров, целых 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 цифр, то выведите само число без ведущих нулей.

n, k = (int(i) for i in input().split())
ab = [1, 1]
d=(10 ** k)
if n < 2:
    fib = 1
else:
    n -= 1
    for i in range(n):
        s = (ab[0] + ab[1]) % d
        ab[0] = ab[1]
        ab[1] = s
        fib = ab[1]
print(fib)