e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
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 (1n106).

Output

Print the number of ways modulo 109 + 7.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
Output example #1
4