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 ≤ n ≤ 106).

Output

Print the number of ways modulo 109 + 7.