CSES: Dice Combinations

 Dice Combinations

Your task is to count the number of ways to construct sum n$n$ by throwing a dice one or more times. Each throw produces an outcome between 1$1$ and 6$6$.

For example, if n=3$n=3$, there are 4$4$ ways:

• 1+1+1$1+1+1$
  
• 1+2$1+2$
  
• 2+1$2+1$
  
• 3$3$
  

Input

The only input line has an integer n$n$.

Output

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

Constraints

• 1≤n≤106$1\le n\le {10}^6$
  

Example

Input:
3

Output:
4