Cho số nguyên dương ~n~, hãy đếm số cách biến đổi số ~1~ thành số ~n~ bằng dãy các thao tác sau:

• Thao tác ~D~: Nhân đôi số hiện tại;
• Thao tác ~T~: Nhân ba số hiện tại;
• Thao tác ~P~: Cộng ~1~ vào số hiện tại.

Ví dụ, ~n=3~, ta có 3 cách ~DP~ hoặc ~PP~ hoặc ~T~.

Input

• Một số nguyên dương ~n~ ~(n \le 1000)~.

Output

• Một số nguyên là số cách biến đổi thỏa mãn.

Sample Input

3

Sample Output

3