Η Florence είναι ένα μικρό panda, το οποίο ζει στην Ταϊλάνδη. Μία μέρα, αποφάσισε να επισκεφθεί τον γνωστό ναό Wat Phra That Doi Suthep, ο οποίος είναι κτισμένος στην πλαγιά ενός μεγάλου και απότομου βουνού. Η πρόσβαση στο ναό είναι εφικτή από μία τεράστια σκάλα.

Η Florence παίρνει θέση μπροστά στην σκάλα, αντικρίζοντας απέναντί της τα Ν σκαλοπάτια. Ανεβαίνοντας την σκάλα, μπορεί να ανέβει κάθε φορά, ένα ή δύο σκαλοπάτια. Επειδή η ανάβαση θα είναι κουραστική, η Florence άρχισε να σκέφτεται με πόσους διαφορετικούς τρόπους μπορεί να ανέβει την μεγάλη αυτή σκάλα, αν κάθε φορά μπορεί να ανέβει ένα ή δύο σκαλοπάτια μαζί.

Δεδομένα εισόδου

Η μοναδική γραμμή της εισόδου, θα περιέχει ένα ακέραιο αριθμό Ν (1 <= Ν <= 45), το πλήθος των σκαλοπατιών που έχει η σκάλα και τα οποία πρέπει να ανέβει η Florence.

Δεδομένα εξόδου

Ένας ακέραιος αριθμός, το πλήθος των τρόπων με τους οποίους μπορεί να ανέβει η Florence τη σκάλα με τα Ν σκαλοπάτια.

Παράδειγμα εισόδου 1

1

Παράδειγμα εξόδου 1

1

Παράδειγμα εισόδου 2

2

Παράδειγμα εξόδου 2

2

Παράδειγμα εισόδου 3

4

Παράδειγμα εξόδου 3

5