Tras poner fin a su carrera internacional de fútbol, Cristiano Ronaldo decidió que quería convertirse en ciudadano de Niue. Para ello, debe aprobar un examen sobre las tradiciones y la cultura de Niue. Respondió fácilmente a todas las preguntas salvo la última, así que necesita tu ayuda. ¿Puedes ayudar a Ronaldo a convertirse en ciudadano de Niue? Esta es la última pregunta:
«Para un arreglo $a_1,a_2,\ldots,a_n$ de enteros positivos, definimos su grado de pertenencia nativa como $\sum_{i=1}^{n} a_i \cdot f_i$, donde $f_0=1$, $f_1=1$ y, para $i\ge 2$, $f_i=a_{i-1}f_{i-1}+f_{i-2}$.
Además, llamaremos niueano a un arreglo si es lexicográficamente menor que su reverso.
Se te da un entero $m$. Calcula cuántos arreglos niueanos tienen un grado de pertenencia nativa no mayor que $m$. Da tu respuesta módulo $998\,244\,353$.»
Entrada
La primera línea contiene un entero $m$ ($1\le m\le 10^{10}$).
Salida
Imprime el número de arreglos módulo $998\,244\,353$.
Ejemplos
Entrada 1
6
Salida 1
1
Entrada 2
7
Salida 2
2
Entrada 3
13
Salida 3
8
Entrada 4
42
Salida 4
114
Entrada 5
67
Salida 5
305
Entrada 6
6767
Salida 6
3471737
Entrada 7
676767
Salida 7
863282261
Entrada 8
67676767
Salida 8
217404956
Entrada 9
6767676767
Salida 9
691869515
Nota
