J. Фибоначчи за логарифм

Вычислите $F_n$ по модулю $10^9 + 7$, где $F_1 = F_2 = 1$ и $F_k = F_{k-1} + F_{k-2}$.

Ограничение на $n$ — до $10^{18}$, так что ни рекурсия по определению, ни цикл не годятся.

Приём: возведение матрицы $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ в степень тем же рекурсивным способом, что и в классной задаче про степень. Умножение матриц два на два — это восемь умножений, а вызовов будет всего около шестидесяти.

Одна строка содержит число $n$ ($1 \le n \le 10^{18}$).

Одно число — $F_n$ по модулю $10^9 + 7$.