Šeštadieninė informatikos olimpiadininkų mokykla

Turime keturių rūšių vagonus: pašto, krovininius, keleivinius ir vagonus restoranus. Iš šių vagonų reikia suformuoti traukinio sąstatą. Vagonus galima sukabinti laikantis tokių taisyklių:

1. pašto vagonas gali būti kabinamas tik po garvežio (sąstato pradžioje) arba po kito pašto vagono. Sąstate gali būti ne daugiau kaip 2 pašto vagonai (jų gali ir visai nebūti);
2. vagonas restoranas turi būti tarp dviejų keleivinių vagonų. Restoranų skaičius neribojamas, tačiau jų gali ir visai nebūti;
3. sąstate būtinai turi būti bent vienas keleivinis vagonas. Šios rūšies vagonų skaičius neribojamas;
4. krovininiai vagonai kabinami tik sąstato gale, vienas po kito. Jų gali būti ne daugiau kaip trys (gali ir visai nebūti)

Užduotis

Reikia sukabinti vagonų. Parašykite programą, kuri suskaičiuotų, keliais skirtingais būdais galima suformuoti traukinio sąstatą.

Pastaba. Garvežys neįskaitomas į sąstatą.

Pradiniai duomenys

Pradinis duomuos: vagonų skaičius .

Rezultatai

Rezultatas – vienas sveikasis skaičius. Variantų skaičius gali viršyti maxint reikšmę, todėl naudokite tipą longint.

Pavyzdžiai

13

1042

Ribojimai

$1 \leq n \leq 43