Косукэ слишком ленив. Он не даст вам никакой легенды, только задачу:
Числа Фибоначчи определяются следующим образом:
- \(f(1)=f(2)=1\).
- \(f(n)=f(n-1)+f(n-2)\) \((3\le n)\)
Мы обозначаем
\(G(n,k)\) как индекс
\(n\)-го числа Фибоначчи, которое делится на
\(k\). Для заданных
\(n\) и
\(k\) вычислите
\(G(n,k)\).
Поскольку это число может быть слишком большим, выведите его по модулю \(10^9+7\).
Например: \(G(3,2)=9\), потому что \(3\)-е число Фибоначчи, которое делится на \(2\), равно \(34\). \([1,1,\textbf{2},3,5,\textbf{8},13,21,\textbf{34}]\).
Выходные данные
Для каждого набора входных данных выведите единственное число: значение \(G(n,k)\), взятое по модулю \(10^9+7\).