Dice Combinations#9036

Dice Combinations

1 second

128 megabytes

Very easy

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$ n = 3, there are $4$ ways:

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

Input

One integer $n (1 \leq n \leq 1 0^{6})$ n~(1 \le n \le 10^6).

Output

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

Examples

Example 1

Loading

Example 4

Loading

Example 5

Loading

Example 7

Loading

n = 3

1 + 1 + 1

1 + 2

2 + 1

n (1 \leq n \leq 1 0^{6})

1 0^{9} + 7