Dãy Tribonacci được định nghĩa như sau:

• T₁ = 1

• T₂ = 1

• T₃ = 2

• Tₙ = Tₙ₋₁ + Tₙ₋₂ + Tₙ₋₃ với n ≥ 4

Các số đầu tiên của dãy là: 1 1 2 4 7 13 24 44 81 ...

Cho số nguyên dương ~N~. Hãy tính số hạng thứ ~N~ của dãy Tribonacci.

Dữ liệu vào:

• Gồm một dòng chứa số nguyên dương ~N~.

Dữ liệu ra:

• In ra giá trị của số hạng thứ ~N~.

Ràng buộc

~1 ≤ N ≤ 50~

Ví dụ

Input

8

Output

44