Задачи
Комбинации игральных костей
Комбинации игральных костей
Подсчитайте количество способов, которыми можно получить сумму $n$, бросая игральный кубик один или несколько раз. Каждый бросок дает результат между $1$ и $6$.
Например при $n = 3$ имеется $4$ способа:
\begin{itemize}
\item $1 + 1 + 1$
\item $1 + 2$
\item $2 + 1$
\item $3$
\end{itemize}
\InputFile
Одно целое число $n~(1 \le n \le 10^6)$.
\OutputFile
Выведите количество способов по модулю $10^9 + 7$.
Входные данные #1
3
Выходные данные #1
4
Входные данные #4
4
Выходные данные #4
8
Входные данные #5
5
Выходные данные #5
16
Входные данные #7
7
Выходные данные #7
63