Dice Combinations

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Count the sequences of dice throws whose values sum to $n$. Each throw is between 1 and 6, and order matters.

Input

The only line contains integer $n$.

Output

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

Subtasks

• Subtask 1 — 20 points: 1 <= n <= 15.
• Subtask 2 — 30 points: 1 <= n <= 10000.
• Subtask 3 — 50 points: 1 <= n <= 1000000.

Examples

Input

3

Output

4

Explanation

For $n=3$, the four sequences are $1+1+1$, $1+2$, $2+1$, and $3$.