Trong một lễ hội thu hút nhiều du khách, có một trò chơi dân gian đơn giản nhưng đầy thử thách mang tên "Nhảy Lò Cò." Nhiệm vụ của người chơi là hoàn thành quãng đường dài \(n\) mét. Mỗi người tham gia có thể lựa chọn cách di chuyển bằng ba kiểu nhảy khác nhau với độ dài lần lượt là \(1\) mét, \(2\) mét, hoặc \(3\) mét cho mỗi bước nhảy. Để chiến thắng trò chơi, người chơi phải tìm ra các cách nhảy sao cho tổng chiều dài của các bước nhảy đúng bằng \(n\) mét. Mỗi cách nhảy hợp lệ được coi là một phương án di chuyển chính xác để hoàn thành trò chơi.

Yêu cầu:

• Cho \(n\), gọi \(K\) là số cách di chuyển đúng khác nhau để đi hết đoạn đường \(n\) mét, hãy tính phần dư của \(K\) chia \(1e9+7\).

Dữ liệu vào

• Số nguyên dương \(n\)

Dữ liệu ra

• Một số nguyên là phần dư của \(K\) chia \(1e9+7\).

Input 1

5

Output 1

13

Ràng buộc

• Có \(20%\) số test ứng với \(20%\) số điểm có \(n \le 20\);
• Có \(40%\) số test ứng với \(40%\) số điểm có \(n \le 10^6\);
• Có \(40%\) số test ứng với \(40%\) số điểm có \(n \le 10^{15}\);