Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: kamuoliukai.in

Rezultatų failas: kamuoliukai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Raudoni ir balti kamuoliukai

Turite neribotą kiekį raudonų ir baltų kamuoliukų. Tos pačios spalvos kamuoliukai sveria tiek pat, raudoni yra sunkesni už baltus.

Reikia į eilę išdėstyti N kamuoliukų taip, kad kiekvienas kamuoliukas nelyginėje pozicijoje būtų ne sunkesnis už kaimyninius kamuoliukus ir kiekvienas kamuoliukas lyginėje pozicijoje būtų ne lengvesnis už kaimyninius. Kitaip tariant, reikia sudaryti seką a_1,a_2,\\dots,a_N, kur a_i yra kamuoliuko, esančio pozicijoje i, svoris, taip kad būtų teisinga nelygybė:

a_1\\lea_2\\gea_3\\lea_4\\ge\\dots

Kiek skirtingų sekų galima sudaryti?

Pradiniai duomenys

Vienintelėje eilutėje yra vienas sveikasis skaičius N (1\\leN\\le50\\000).

Rezultatai

Vienoje eilutėje programa turi įrašyti galimų sekų kiekį.

Pavyzdžiai

Duomenys Rezultatai 
1
 
2
 
3
 
5