Pintando las ventanas.

Submit solution
Points: 100 (partial)
Time limit: 1.0s
Memory limit: 16M
Author:
FrankHG
Problem type
Allowed languages
C, C#, C++, Java, JS, Pascal, Python, VB

La gerencia de la tienda de estimulación a los azucareros del centro decidió pintar las ventanas con franjas de color blanco, azul y rojo. Ellos quieren satisfacer las siguientes condiciones:

• Franjas del mismo color no pueden ser colocadas una detrás de otra.

• Una franja azul siempre tiene que ser colocada entre una blanca y una roja o entre una roja y una blanca.

Escriba un programa que ayude a la gerencia de la tienda a contar la cantidad de formas de pintar su tienda. Como la respuesta puede ser muy larga imprímala módulo 10^9+7.

Entrada

La primera y única línea contiene en número n (1 \leq n \leq 10^7) , la cantidad de franjas.

Salida

En una única línea imprima la respuesta del problema módulo 10^9+7 .

Ejemplo #1 de Entrada

3

Ejemplo #1 de Salida

4

Ejemplo #2 de Entrada

54321

Ejemplo #2 de Salida

111378255

Explicación del primer ejemplo:

Comments


  • 3
    linkyless  commented on Jan. 5, 2024, 10:17 p.m.

    Gente, ¿pueden comentarme alguna idea para este ejercicio? No entiendo muy bien cómo empezar y no sé muy bien cómo usar la exponenciación de matrices en el código. Gracias.


    • 3
      karellgz  commented on Jan. 5, 2024, 11:19 p.m.

      Espero esta idea te ayude (no me borren el comentario, es solo una idea, no la solucion):

      La cantidad de franjas de tamanho N que terminan en color X depende de la cantidad de franjas de tamanho N-1 que terminan en color Y, color Z ...


      • 2
        linkyless  commented on Jan. 6, 2024, 3:12 a.m.

        Muchas gracias. Funcionó. Un abrazo <3


    • 4
      Marco_Escandon  commented on Jan. 5, 2024, 11:09 p.m.

      Se puede resolver usando dp


  • 2
    karellgz  commented on Jan. 2, 2024, 2:31 a.m.

    Bonus: resuelvanlo para 1 \le N \le 10^{18}

    :)


    • 2
      josue  commented on Jan. 3, 2024, 8:12 p.m.

      Me arriesgaría a decir que matrix power