Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Difficulty Alpha
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
Для отправки решений необходимо выполнить вход.
|