munte

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 $2 \cdot n - 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:
  • pas pe orizontală de lungime $2$, deci de tipul $(2, 0)$
  • pas „în sus” de lungime $1$, deci de tipul $(1, 1)$
  • 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 și precizări

• $1 \leq n \leq 100$
• Pentru $60\%$ din teste rezultatul este un întreg pe $64$ de biţi.

Exemplul 1

munte.in

1

munte.out

1

Explicație

Lungimea drumului fiind $2 \cdot 1 - 2 = 0$, există o singură modalitate de a traversa muntele (aceea de a sta pe loc)

Exemplul 2

munte.in

2

munte.out

1

Explicație

Lungimea drumului fiind $2 \cdot 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.

Exemplul 3

munte.in

3

munte.out

3

Explicație

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.