Siz zinapoyaga chiqayapsiz. Yuqoriga chiqish uchun n ta zina bor. Har safar siz ko'tarilishingizda 1 yoki 2 qadam qo'yishingiz mumkin. Siz necha xil usulda cho'qqiga chiqishingiz mumkin?
Masalan.
1-misol Kiritish: n = 2
Chiqarish: 2
Tushuntirish: Bunda ikkita usu1 bilan eng yuqoriga chiqish mumkin.
1. 1 zina + 1 zina
2. 2 zinalar


2-misol
Kiritish: n = 3
Chiqarish: 3
Tushuntirish: Bunda uchta usu1 bilan eng yuqoriga chiqish mumkin.
1. 1 zina + 1 zina + 1 zina
2. 1 zina + 2 zinalar
3. 2 zinalar + 1 zina


Входные данные:
N (1 <= N <= 45) berilgan.

Выходные данные:
Zinani eng tepasiga necha xil usulda chiqishlar sonini yozing.