Salto de rana

Submit solution
Points: 100 (partial)
Time limit: 1.0s
Java 8 2.0s
Python 2.0s
Memory limit: 64M
Java 8 128M
Python 128M
Author:
ralcolea
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Existe una especie de rana que se considera especial por su forma de saltar. Cada rana de esta especie puede avanzar exactamente uno o dos pasos en cada salto, siempre en línea recta. Para este problema se desea conocer, dado un camino de N pasos, ¿cuál es la cantidad de formas posibles en que una rana de esta especie puede alcanzar el final del camino?

Entrada

La primera línea de la entrada contiene un número T (1 \le T \le 100) de casos de prueba. Cada una de las siguientes T líneas representa un caso de prueba. Cada caso de prueba contiene un entero positivo con el número N (1 \le N \le 10\,000) de pasos correspondiente a un camino.

Salida

Para cada caso de prueba, imprima el número de formas posibles en que la rana puede alcanzar el final del camino. Como este número puede ser muy grande, imprima el valor de la solución modulo 1\,000\,000\,007.

Ejemplo de entrada

4
1
4
10
25

Ejemplo de salida

1
5
89
121393

Comments


  • -6
    penta_D  commented on March 29, 2023, 3:43 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -7
      Luis_E  commented on Jan. 15, 2024, 3:47 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • 9
      LeandroGamer  commented on Aug. 29, 2023, 8:52 p.m.

      Este ejercicio se puede responder usando la sucesión de Fibonacci, creo que con este dato es suficiente, si te doy otro dato ya te estaría resolviendo el problema.