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\le n\le 10^6)$.

Output

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

Examples