Într-un depou de vagoane
liniile sunt construite într-un mod special: există o linie de INTRARE,
pe care se găsesc cele N vagoane ale unei garnituri,
o linie de MANEVRĂ pe care
pot intra vagoane doar de pe linia de intrare, şi o linie de IEŞIRE pe care pot intra vagoane doar de pe linia de manevră. Cele N vagoane de pe linia de
intrare sunt numerotate de la 1 la N, dar ele se găsesc pe linia de intrare într-o ordine
oarecare. Utilizând linia de manevră, trebuie să formăm pe linie de ieşire o garnitură de tren cu vagoanele în ordinea crescătoare a numerelor lor.
Astfel,
dacă pe linia de INTRARE se găseşte o garnitură cu 3 vagoane în ordinea 3,
1, 2 atunci realizând pe rând operaţiile:
- vagonul 3 intră de pe linia de INTRARE pe linia de MANEVRĂ
- vagonul 1 intră de pe linia de INTRARE pe linia de MANEVRĂ
- vagonul 1 intră pe linia de IEŞIRE de pe linia de MANEVRĂ
- vagonul 2 intră de pe linia de INTRARE pe linia de MANEVRĂ
- vagonul 2 intră pe linia de IEŞIRE de pe linia de MANEVRĂ
- vagonul 3 intră pe linia de IEŞIRE de pe linia de MANEVRĂ
Garnitura care se formează pe linia de IEŞIRE va fi 1, 2, 3.
Dacă insă pe linia de INTRARE vagoanele se găsesc în ordinea 2, 3, 1 nici o succesiune de operaţii nu permite ca garnitura să poată fi ordonată crescător pe linia de IEŞIRE.
Cerinţă
Scrieţi un program
care sa determine în câte moduri distincte
pot exista cele N vagoane pe linia de INTRARE astfel încât să existe o succesiune
de operaţii care să permită ordonarea vagoanelor pe linia de ieşire.
Date de intrare
Fişierul de intrare manevre.in conţine pe prima linie numarul natural N indicând numărul de vagoane din care este formată garnitura.
Date de ieşire
Fişierul de iesire manevre.out va conţine pe prima linie un număr natural
indicând în câte moduri distincte pot exista vagoanele pe linia de INTRARE astfel încât să existe o modalitate
de manevrare a acestora pentru a le pune pe linia de IEŞIRE în ordinea crescătoare a numerelor vagoanelor.
Restricţii
1 <= N <= 100
40% dintre datele de intrare au N <= 10
Exemple
manevre.in
manevre.out
Explicaţie
3
5
Cele 5 garnituri posibile pe
linia de intrare sunt: 123, 132, 213, 312, 321. Garnitura 231 nu poate fi manevrată pentru a fi pusă în ordine.
