Las escaleras de la ETSINF

En la ETSINF hay una escalera con $n$ escalones. Cada vez que subes, puedes avanzar 1 o 2 escalones. Para varios valores de $n$, determina de cuántas formas distintas se puede subir la escalera exactamente hasta el último escalón. Como el número de formas puede ser muy grande, muestra el resultado módulo 10022026. ## Entrada Un entero $t$, el número de casos de prueba. En cada caso, un entero no negativo $n$, que representa el número de escalones. Se garantiza que no habrá más de $2 \cdot 10^5$ escalones ni $2 \cdot 10^5$ casos de prueba. ## Salida Para cada caso, imprime el número de formas de subir la escalera en módulo 10022026.

6
1
2
3
4
5
25729

1
2
3
5
8
7501649