Competitions
Dynamic programming - linear
Dice Combinations
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
One integer n (1 ≤ n ≤ 106
).
Output
Print the number of ways modulo 109
+ 7.
Input example #1
3
Output example #1
4
Input example #4
4
Output example #4
8
Input example #5
5
Output example #5
16
Input example #7
7
Output example #7
63