An và Bình cùng tham gia câu lạc bộ Toán vui của trường. Trong buổi sinh hoạt đầu tiên, thầy Lan giới thiệu một dãy số đặc biệt mà thầy đã nghĩ ra: ba số đầu tiên của dãy đều bằng \(1\), còn từ số thứ tư trở đi, mỗi số bằng tổng của đúng ba số liền trước nó. Hai bạn ngồi tính thử và rất ngạc nhiên vì dãy cứ lớn lên rất nhanh.

Thầy Lan thách đố: nếu cho biết số thứ tự \(N\), hãy tính giúp thầy số hạng tương ứng trong dãy. Vì số hạng có thể rất lớn nên chỉ cần đưa ra phần dư khi chia cho \(10^9 + 7\).

Hãy giúp An và Bình hoàn thành thử thách của thầy Lan.

Định dạng đầu vào

• Một dòng duy nhất chứa số nguyên \(N\) (\(1 \le N \le 10^7\)).

Định dạng đầu ra

• In ra số hạng thứ \(N\), lấy phần dư khi chia cho \(10^9 + 7\).

Ví dụ

Input:

5

Output:

5

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 20\).
• \(30\%\) số điểm ứng với \(N \le 10^5\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.