# Dice Combinations

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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≤10_{6})$.

## Output

Print the number of ways modulo $10_{9}+7$.

## Examples

Input #1

Answer #1

Input #4

Answer #4

Input #5

Answer #5

Input #7

Answer #7

Submissions 5K

Acceptance rate 31%