Nhiệm vụ của bạn là đếm số cách tạo ra tổng bằng \(n\) bằng cách gieo xúc xắc một hoặc nhiều lần.
Mỗi lần gieo sẽ cho ra một kết quả nằm trong khoảng từ \(1\) đến \(6\).
Ví dụ, nếu \(n = 3\), có \(4\) cách như sau:

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

Input

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

Output

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

Input

3

Output

4