Bạn có một con xúc xắc. Bạn sẽ lắc con xúc xắc sao cho tổng các chấm trên các lần xúc là \(n\).

Cho trước \(n(\leq 10^6)\). Hãy đếm số cách lắc ? (module \(10^9 + 7\))

Ví dụ

\(n = 3\) thì có $ 4$ cách:

• \(1 + 1 + 1\)

• \(1 + 2\)

• \(2 + 1\)

• \(3\)

Input

3

Output

4