Frog SPOJ.

Một con ếch có thể nhảy 1, 2, 3 bước để có thể lên đến một đỉnh cần đến. Hãy đếm số các cách con ếch có thể nhảy đến đỉnh.

Input Format

Số nguyên dương N mô tả số bước con ếch cần di chuyển để nhảy tới đỉnh.(1<=N<=40)Vì đáp án sẽ rất lớn nên bạn hãy mode với 1e9+7.

Constraints

.

Output Format

In ra kết quả của bài toán

Ví dụ:

Dữ liệu vào

7

Dữ liệu ra

44