|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Сложность Альфа
Your task is to count the number of ways to construct sum n
by throwing a dice one or more times. Each throw produces an outcome between 1
and 6
.
For example, if n=3
, there are 4
ways:
1+1+1
1+2
2+1
3
Input
The only input line has an integer n
.
Output
Print the number of ways modulo 109+7
.
Constraints
1≤n≤106
Example
Input:
3
Output:
4
Для отправки решений необходимо выполнить вход.
|