Квадраты Фибоначчи

Оказывается, что

$$$$$$\sum\limits_{i = 0}^{n} f_i^2 = f_n \cdot f_{n + 1}$$$$$$

Докажем это по индукции. База: $$$n = 0$$$

$$$$$$\sum\limits_{i = 0}^{0} f_i^2 = 1 = f_0 \cdot f_1$$$$$$

Переход: знаем, что

$$$$$$\sum\limits_{i = 0}^{n} f_i^2 = f_n \cdot f_{n + 1}$$$$$$

Прибавим к обоим частям по $$$f_{n + 1}^2$$$

$$$$$$\sum\limits_{i = 0}^{n + 1} f_i^2 = f_n \cdot f_{n + 1} + f_{n + 1} \cdot f_{n + 1}$$$$$$

$$$$$$\sum\limits_{i = 0}^{n + 1} f_i^2 = f_{n + 1} \cdot (f_n + f_{n + 1})$$$$$$

$$$$$$\sum\limits_{i = 0}^{n + 1} f_i^2 = f_{n + 1} \cdot f_{n + 2}$$$$$$

Осталось научиться вычислять $$$n$$$-е число Фибоначчи по модулю. Это достаточно стандартная задача на оптимизацию динамического программирования возведением матрицы в степень. Подробнее можно почитать, например, здесь: https://e-maxx.ru/algo/fibonacci_numbers.