Nhiệm vụ của bạn là tính số cách để đạt được tổng ~n~ bằng cách gieo xúc xắc. Mỗi lần gieo cho một số nguyên 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~ và ~1+1+6+1+1~.

Dữ liệu vào

Dòng duy nhất chứa một số nguyên ~n~.

Kết quả

In ra số cách modulo ~10^9+7~.

Giới hạn

• ~1 \le n \le 10^{18}~

Ví dụ

Dữ liệu vào:

8

Kết quả:

125