Ovi este un băieţel foarte isteţ căruia îi place să scrie pe asfalt cu creta şi să ţopăie. El desenează cu cretă roşie un dreptunghi de lăţime exact 2 metri şi lungime N metri, pe care îl împarte în pătrate egale de latură 1 metru, unele laturi interioare fiind desenate cu cretă roşie, iar restul laturilor interioare cu cretă albă. Ovi porneşte din pătratul aflat în colţul stânga sus al dreptunghiului, sărind dintr-un pătrat în altul vecin pe linie sau coloană, cu condiţia ca latura care desparte cele două pătrate să nu fie colorată în roşu. El îşi doreşte ca prin sărituri succesive să ajungă în toate pătratele dreptunghiului, dar a observat că numai pentru anumite variante de colorare a laturilor pătratelor reuşeşte acest lucru.
În exemplele de mai jos (cu N=2) liniile interioare îngroşate sunt colorate cu roşu, iar cele punctate sunt colorate cu alb. La exemplul din fig. 1, pornind din colţul stânga sus se poate ajunge în oricare alt pătrat, dar în exemplul din fig. 2 nu se poate ajunge la pătratele din partea dreaptă.
Cerinţă
Ajutaţi-l pe Ovi să numere câte posibilităţi de colorare în roşu a unor laturi interioare ale pătratelor sunt astfel încât plecând din colţul stânga sus să poată ajunge prin sărituri în oricare alt pătrat.
Date de intrare
În fişierul patrate.in se află un singur număr natural N ce reprezintă lungimea în metri a dreptunghiului.
Date de ieşire
În fişierul patrate.out veţi scrie un singur număr natural (urmat de caracterul de sfârşit de linie) ce reprezintă numărul de posibilităţi cerut.
Restricţii şi precizări
2 <= N <= 1000
Exemplu
patrate.in
2
patrate.out
5
Explicaţie
Cele 5 posibilităţi sunt:
