SPOJ in Gyumri

   Գնացքում կան չորս տեսակի վագոններ՝ փոստային, բեռնատար, ուղևորատար վագոններ և շարժական ռեստորաններ: Գնացքը ձևավորելիս վագոնները պետք է զուգորդվեն՝ բավարարելով հետևյալ կանոններին.


Փոստային      վագոնները կարող են միանալ միայն շարժիչին, այսինքն լինել գնացքի սկզբում կամ      կարող են միանալ մեկ այլ փոստային վագոնի: Նշենք, որ կարող են լինել երկուսից      ոչ ավել փոստային վագոններ և վերջիններս կարող են իսպառ բացակայել:
Շարժական      ռեստորանները պետք է լինեն երկու ուղևորատարների միջև, վերջիններիս քանակն      անսահմանփակ է, բայց նրանք կարող բացակայել:
Առնվազն      մեկ      ուղևորատար վագոն պետք է գոյություն ունենա      գնացքում: Այս տեսակի վագոնների      թիվը անսահմանափակ է:
Բեռնատար      վագոնները պետք է լինեն գնացքի վերջում և կցված մեկը մյուսի հետևից: Բեռնատար      վագոնների թիվը չպետք է գերազանցի 3-ը, նրանք կարող են ընդհանրապես չլինել:

   Անհրաժեշտ է միացնել n վագոններ: Գրել ծրագիր, որը կհաշվի թե քանի՞ եղանակով է դա հնարավոր կատարել: 
Մուտքային տվյալներ
  Մուտքի միակ տողում տրված է n (1≤n≤40) բնական թիվը:
Ելքային տվյալներ
  Միակ տողում պետք է արտածել խնդրի պատասխանը
Օրինակներ՝




N


stdin


stdout




1


1


1




2


2


3