Nhiệm vụ của bạn là tính toán số cách để có được một tổng \(n\) bằng cách gieo xúc xắc. Mỗi lần gieo mang lại một số nguyên giữa \(1\ldots6\).

Ví dụ: nếu \(n = 10\), một số cách có thể là \(3 + 3 + 4\), \(1 + 4 + 1 + 1 + 4\) và \(1 + 1 + 6 + 1 + 1 + 1\).

Input

• Dòng đầu vào duy nhất chứa một số nguyên \(n\).

Output

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

Constraints

• \(1 \leq n \leq 10 ^ {18}\)

Example

Sample input

8

Sample output

125