Khiêm dạo này thích chơi mấy trò liên quan đến xúc xắc. Cậu đang nghiên cứu xem có bao nhiêu cách tung xúc xắc mà tổng số điểm các lần tung là \(n\), biết xúc xắc có điểm từ \(1\) đến \(6\).

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

Mọi người hãy giải quyết vấn đề này cùng Khiêm nhé.

Đầu vào

Một dòng duy nhất chứa số tự nhiên \(n\).

Đầu ra

Một số tự nhiên duy nhât là số cách tung xúc xắc có tổng điểm bằng \(n\). Trường hợp số rất lớn chia dư cho \(10^9 + 7\).

Giới hạn

\(1 ≤ n ≤ 10^{18}\)

\(30\%\) số test có \(n \le 10\).

Ví dụ:

Đầu vào:

8

Đầu ra:

125