Nem Tudo é Greve Versão Hard
Por Roger Eliodoro Condras, UFSC-ARA 
Brazil
Por Roger Eliodoro Condras, UFSC-ARA Brazil
Uma vez, enquanto estudavamos pra Maratona de Porgramção, Tobias e eu nos deparamos com um problema interesante, espero que vocês também gostem.
Existe uma escada com N degraus. Você pode escolher entre descer 1, 2, ou 3 degraus por vez a cada movimento. De quantas maneiras diferentes você poderia descer essa escada com N degraus?
Um único número inteiro N (1 ≤ N ≤ 100.000), o número de degraus na escada.
Um único inteiro, o número combinações de formas diferentes de descer a escada. A resposta pode ser um pouco grande, então imprima o resto da divisão pelo nosso primo favorito (109+7).
| Exemplos de Entrada | Exemplos de Saída |
|
1 |
1 |
|
5 |
13 |
|
1000 |
509672692 |