URI Online Judge | 2986

Nem Tudo é Greve Versão Hard

Por Roger Eliodoro Condras, UFSC-ARA BR Brazil

Timelimit: 1

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?

Entrada

Um único número inteiro N (1 ≤ N ≤ 100.000), o número de degraus na escada.

Saída

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