Gigel este un pasionat excursionist. Îi plac în special excursiile la munte. La sfârşitul acestei săptămâni el şi-a propus să traverseze un munte din apropierea oraşului Cluj. Atâta doar că echipa Salvamont locală i-a impus nişte condiţii:
– lungimea drumului trebuie să fie exact 2n-2 metri, valoarea n fiind dată de salvamontişti;
– trebuie să plece de la poalele muntelui şi trebuie să ajungă tot la poalele muntelui de partea cealaltă la aceeaşi altitudine;
– nu are voie să coboare sub altitudinea de plecare;
– poate traversa drumul doar folosind trei tipuri de paşi:
1) pas pe orizontală de lungime 2, deci de tipul (2, 0)
2) pas „în sus” de lungime 1, deci de tipul (1, 1)
3) pas „în jos” de lungime 1, deci de tipul (1, -1)
– drumul lui nu are voie să aibă „vârf” la altitudinea 1, adică nu are voie ca fiind la un moment dat, pe parcursul drumului, la altitudinea de plecare, să facă un pas în sus urmat imediat de un pas în jos.
Cerinţă
Dată fiind valoarea n să se determine în câte moduri poate Gigel să traverseze muntele respectând condiţiile echipei Salvamont.
Date de intrare
Fişierul de intrare munte.in conţine o singură linie pe care se află numărul natural n.
Date de ieşire
Fişierul de ieşire munte.out va conţine o singură linie pe care va fi scris numărul de modalităţi în care Gigel poate realiza traversarea muntelui.
Restricţii
1 ≤ n ≤ 100
Pentru 60% din teste rezultatul este un întreg pe 64 de biţi.
Exemple
munte1.in
munte1.out
Explicaţii
1
1
Lungimea drumului fiind 2*1-2=0, există o singură modalitate de a traversa muntele (aceea de a sta pe loc)
2
1
Lungimea drumului fiind 2*2-2=2, există o singură modalitate de a traversa muntele, printr-un pas de lungime 2.
Varianta din dreapta nu este corectă deoarece nu respectă ultima condiţie.
3
3
Cele 3 modalităţi corecte de a traversa muntele cu un drum de lungime 4 sunt:
Orice alt mod de a traversa muntele pe un drum de lungime 4 este incorect.
