Cho số nguyên dương ~S~. Bạn hãy đếm xem có bao nhiêu dãy số thỏa mãn đồng thời các điều kiện:

• Mỗi phần tử của dãy số có giá trị lớn hơn hoặc bằng ~3~.
• Tổng các phần tử của dãy số bằng chính xác ~S~.

Hai dãy số được gọi là khác nhau nếu thỏa mãn một trong các điều kiện sau:

• Số lượng phần tử của hai dãy số khác nhau.
• Tồn tại một vị trí sao cho giá trị tại vị trí đó của hai dãy số là khác nhau.

Input

• Dòng duy nhất chứa số nguyên ~S~ ~(1 \le S \le 10^4)~.

Output

• In ra số lượng dãy số thỏa mãn với kết quả chia lấy dư cho ~10^9+7~.

Examples

Sample Input

6

Sample Output

2

Scoring

• Subtask ~1~ ~-~ ~500~ điểm: ~S \le 10~
• Subtask ~2~ ~-~ ~1000~ điểm: ~S \le 500~
• Subtask ~3~ ~-~ ~500~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, các dãy số thỏa mãn bao gồm: ~\{3,3\}~ và ~\{6\}~.