XXVI Olimpíada Brasileira de Informática
Submeta sua solução

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 109+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 109+7.

Restrições

  • 0 ≤ N ≤ 104.

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
	

 

Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação