Последовательность, образованная остатками от деления последовательности Фибоначчи на $n$ яыляется периодической для любого положительного целого значения $n$. Ее период зависит от значения $n$. Этот период называется периодом Пизано для $n$ и часто обозначается сокращенно как $\pi(n)$.

Существует три значения $n$, для которых $\pi(n)$ равно $18$: $19$, $38$ и $76$. Сумма значений меньше $50$ равна $57$.

Найдите сумму значений $n$ меньше $1 000 000 000$, для которых $\pi(n)$ равно $120$.