Problem C
Tåget

Tåg kan genom olika vagnar komponeras på olika sätt. Här ska d u skriva ett program som tar reda på hur många. Våra tåg kan innehålla fyra olika typer av vagnar: postvagn (M), personvagn (P), restaurangvagn (R) och godsvagn (G). Loket räknas inte till vagnarna och ingår därför inte i våra kompositioner.

Följande regler gäller för sammansättningen:

• Postvagn kan bara inleda tåget, kopplas direkt efter loket eller efter en annan postvagn. Det kan högst finnas två postvagnar, men behöver inte finnas någon.

• Restaurangvagn måste alltid befinna sig mellan två personvagnar. Det kan finnas hur många som helst men behöver inte finnas någon.

• Det måste finnas minst en personvagn och kan finnas hur många som helst.

• Godsvagn kopplas alltid sist i tåget. En godsvagn kan endast ha en annan godsvagn efter sig. Det får finnas högst tre godsvagnar, men behöver inte finnas någon. Programmet ska fråga efter hur många vagnar tåget innehåller och därefter beräkna och skriva ut antalet olika tåg som kan komponeras.

Indata

Indata består av ett heltal $1 \le n \le 30$ - antalet vagnar i tåget.

Utdata

Ditt program ska skriva ut antalet tåg som kan skapas.

13

1042

4

13