Một con ếch ở bậc thang số ~0~ đang muốn nhảy tới bậc thang số ~n~. Mỗi lần ếch chỉ có thể thực hiện một trong ba bước nhảy cố định:

• Nhảy ~1~ bậc
• Nhảy ~3~ bậc
• Nhảy ~5~ bậc

Hỏi có bao nhiêu cách khác nhau để ếch nhảy đến đúng bậc thang số ~n~. Hai bước nhảy được coi là khác nhau nếu thứ tự thực hiện các bước nhảy là khác nhau. Ví dụ ~\{1, 5\}~ và ~\{5, 1\}~ được coi là hai cách khác nhau.

Dữ liệu vào

Gồm một dòng chứa số nguyên ~n~ ~(1 \leq n \leq 10^{18})~.

Dữ liệu ra

Số cách nhảy khác nhau để ếch đi từ bậc ~0~ đến bậc ~n~ chia dư cho ~10^9+7~.

Ví dụ

Đầu vào

6

Đầu ra

8

Giải thích

Có ~8~ cách để nhảy từ bậc ~0~ đến bậc ~6~, cụ thể là: ~\{1,1,1,1,1,1\}~, ~\{1,1,1,3\}~, ~\{3,1,1,1\}~, ~\{1,3,1,1\}~, ~\{1,1,3,1\}~, ~\{3, 3\}~, ~\{1,5\}~, ~\{5,1\}~.

Tính điểm

• Subtask 1 ~(50\%)~: ~0 \leq n \leq 10^5~.
• Subtask 2 ~(30\%)~: ~0 \leq n \leq 10^7~.
• Subtask 3 ~(20\%)~: ~0 \leq n \leq 10^{18}~.