Có một chú thỏ nâu thích một cô thỏ trắng ở gần cuối khu rừng. Vào một ngày đẹp trời, thỏ nâu quyết định sang rủ thỏ trắng cùng đi ngắm hoa và thưởng thức những củ cà rốt ngon tuyệt mà chú kiếm được. Hang của chú thỏ nâu và cô thỏ trắng cách nhau n mét (n ≤ 10⁹). Do từ nhỏ đã bị vòng kiềng bẩm sinh, mỗi bước thỏ nâu chỉ có thể nhảy xa được 1 mét, 2 mét hay 3 mét theo quy tắc:

Các bước xa 3 mét phải thực hiện trước các bước xa 2 mét. Các bước xa 2 mét phải thực hiện trước các bước xa 1 mét.

Yêu cầu: Đếm số cách nhảy có thể của chú thỏ nâu trên đường đến hang cô thỏ trắng.

Dữ liệu: Vào từ file văn bản BUNNY.INP gồm duy nhất số n nguyên dương (0 ≤ n ≤ 10⁹)

Kết quả: Ghi ra file văn bản BUNNY.OUT một số duy nhất là số cách nhảy của thỏ nâu.

Ví dụ:

Chú ý: Có 60% số test của bài có n ≤ 10⁵