Các con thỏ không bao giờ chết. Ba tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái). Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới. Giả sử từ đầu tháng 1 có một cặp mới ra đời thì đến tháng thứ ~n~ sẽ có bao nhiêu cặp?

Input

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

Output

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

Sample Input 1

4

Sample Output 1

2

Sample Input 2

21

Sample Output 2

1278