e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dynamic Programming - Linear

Комбінації гральних кубиків

Знайдіть кількість способів, якими можна отримати суму n підкидаючи гральний кубик один або декілька разів. Кожне підкидання дає результат від 1 до 6.

Наприклад, якщо n = 3, то є 4 способи:

1 + 1 + 1

1 + 2

2 + 1

3

Вхідні дані

Одне ціле число n (1n106).

Вихідні дані

Знайдіть кількість способів по модулю 109 + 7.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
Вихідні дані #1
4