L_Fibonacci_modulo.py

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

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

Пример 1
Ввод
3 1
Вывод
3
"""


def fibonacci_modulo(n: int, k: int) -> int:
    ab = [1, 1]
    if n < 2:
        return 1
    n -= 1
    for _ in range(n):
        s = (ab[0] + ab[1]) % (10 ** k)
        ab[0] = ab[1]
        ab[1] = s
        fib = ab[1]
    return fib


if __name__ == '__main__':
    n, k = (int(i) for i in input().split())
    print(fibonacci_modulo(n, k))