Дано целое N (12 <= N <= 106). Найти последние 3 цифры числа Фибоначчи FN

У цифр чисел Фибоначчи есть свойство периодичности:

В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом pi(10) = 60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом pi(100) = 300, последние три цифры — с периодом pi(1000) = 1500 (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8)

Поэтому достаточно вычислить первые 1500 чисел Фибоначчи, а дальше уже смотреть на числа, номер которых равен числу по модулю 1500

Думаю можно сделать так:

fibonacchi = [0, 1]

for i in range(2, 1501):
    value = fibonacchi[-1] + fibonacchi[-2]
    fibonacchi.append(value)

number = int(input('Введите номер числа Фибоначчи: '))
pos = number % 1500
print(fibonacchi[pos] % 1000)

Решение в лоб конечно

Для оптимизации можно сделать так - если номер числа < 1500, то не надо собирать предварительную таблицу, а просто последовательно доходим до нужного числа

Еще более эффективная операция - накапливаем список не чисел, а только последних 3 цифр - меньше памяти съедает

fibonacchi = [0, 1]

f1, f2 = 0, 1

for i in range(2, 1501):
    value = f1 + f2
    fibonacchi.append(value % 1000)
    f1, f2 = f2, value

number = int(input('Введите номер числа Фибоначчи: '))
pos = number % 1500
print(fibonacchi[pos])

Один из вариантов.

Заводишь переменную N, и 2 переменные а, b с значениями 0, 1 (по условию F1 F2). Циклом фор с range(N) перебираешь a, b = b, a + b. (Для дальнейшей обработки нас будет интересовать а) После чего меняешь тип данных переменной а на string и с помощью индексации выводишь -1, -2 и -3 элемент

Самое простое решение - считать числа Фибоначчи итеративно. Миллион итераций Питон проделает меньше чем за секунду, если делать вычисления по модулю 1000:

def fib_mod(n, m):
    a = 0
    b = 1
    for _ in range(n):
        b, a = (a + b) % m, b
    return a


print(fib_mod(int(input()), 1000))

$ time echo 1000000 | python fib_mod.py
875

real  0m0.105s
user  0m0.104s
sys   0m0.000s