Nhiệm vụ của bạn là đếm số cách tạo ra tổng \(n\) bằng cách gieo xúc xắc một hoặc nhiều lần. Mỗi lần gieo cho ra số từ \(1\) đến \(6\).

Ví dụ, nếu \(n = 3\), có \(4\) cách:

• \(1 + 1 + 1\)
• \(1 + 2\)
• \(2 + 1\)
• \(3\)

Input

• Dòng đầu vào duy nhất có số nguyên \(n\).
• Giới hạn: \(1 \leq n \leq 10^6\)

Output

• In số cách chia lấy dư cho \(10^9 + 7\).

Example

3

4