Dice Combinations Cses Problem set problem code solution

 Dice Combinations Cses Problem set problem code solution -

Dice Combinations Cses Problem set problem code solution  dynamic programming code.

Problems statement-

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

link-https://cses.fi/problemset/task/1633/

solution-