Qua được con đường, BabyOrange và hoangks7 tới một khe nứt vực thẳm. Bắc ngang qua nó là một cây cầu treo dài \(n\) mét. Cả hai người có thể nhảy 1 mét, 2 mét hoặc 3 mét mỗi bước nhảy, và họ đều nhảy cùng lúc. Nhiệm vụ của bạn là tính số cách để họ nhảy qua bên kia. Vì kết quả có thể rất lớn, nên chỉ lấy phần dư khi chia cho \(10^9 + 7\)

Input

• Một dòng duy nhất chứa số \(n\) \((1 \le n \le 10^{18})\)

Output

• Một dòng chứa số cách sau khi chia lấy dư cho \(10^9 + 7\)

Example

3

4