Submeta sua solução

Arquivo:

Linguagem: Selecione C++17 / g++ C17 / gcc Javascript Java / JDK Python 3 / CPython

Submete

Nome do arquivo: muro.x, onde x deve ser c, cpp, java, js ou py

Muro

Nós temos dois tipos de tijolos, como mostrado na parte esquerda da figura abaixo. A ideia é construir uma mureta de altura 2 e comprimento N. A parte direita da figura ilustra uma forma de usar os dois tipos de tijolos para construir uma mureta de comprimento N=12.

Precisamos saber quantas formas distintas existem de construir a mureta com esses dois tipos de tijolos. Para isso, já temos duas observações: qualquer mureta de comprimento N vai terminar de uma das sete maneiras ilustradas abaixo e; o número de formas distintas de construir uma mureta de comprimento 2, 1 e 0 é, respectivamente, 5, 1 e 1 (sim! Existe uma forma de construir a mureta de comprimento 0: usar nenhum tijolo). Dado N, seu programa deve computar o número de formas distintas de construir uma mureta de comprimento N. Como esse número pode ser muito grande, seu programa deve imprimir o resto da divisão dele por 10⁹+7.

Entrada

A única linha da entrada contém um inteiro N, representando o comprimento da mureta.

Saída

Imprima uma linha contendo um inteiro, o número de formas distintas de construir a mureta com os dois tipos de tijolos. Imprima o resto da divisão desse número por 10⁹+7.

Restrições

• 0 ≤ N ≤ 10⁴.

Informações sobre a pontuação

• Para um conjunto de casos de teste valendo 20 pontos, N ≤ 16.

Exemplos

Entrada 2

Saída 5

 

Entrada 11

Saída 36543

 

Entrada 6

Saída 241

 

Entrada 0

Saída 1

 

Entrada 8712

Saída 844673301