eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Комбинации игральных костей

Комбинации игральных костей

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

Например при n = 3 имеется 4 способа:

  • 1 + 1 + 1

  • 1 + 2

  • 2 + 1

  • 3

Входные данные

Одно целое число n~(1 \le n \le 10^6).

Выходные данные

Выведите количество способов по модулю 10^9 + 7.

Пример

Входные данные #1
3
Выходные данные #1
4
Входные данные #4
4
Выходные данные #4
8
Входные данные #5
5
Выходные данные #5
16
Входные данные #7
7
Выходные данные #7
63