Code Submission Evaluation System Login

CSES Problem Set

Dice Combinations


Task | Statistics


CSES - Dice CombinationsCSES - Dice Combinations

Time limit:1.00 s Memory limit:512 MB

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: Input

The only input line has an integer $n$.

Output

Print the number of ways modulo $10^9+7$.

Constraints
Example

Input:
3

Output:
4