Nhiệm vụ của bạn là tính số cách để thu được tổng bằng n bằng cách tung các viên xí ngầu. Mỗi lần tung cho một số nguyên trong khoảng 1…6. Thứ tự các lần tung được coi là khác nhau (ví dụ 1+2 khác 2+1).

Ví dụ: với n = 10, một vài cách hợp lệ 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~.

Dữ liệu ra:

In ra số cách lấy tổng n, lấy modulo 10^9+7.

Ràng buộc:

~1 ≤ n ≤ 10^{18}~

Ví dụ :

Input:

8

Output:

125