Fie un număr natural N. Dintre toate permutările {p1, p2, ..., pN} ale mulţimii {1, 2, ..., N}, le luăm în considerare numai pe acelea care îndeplinesc condiţia că {p1, p2, ..., pK} nu formează o permutare a mulţimii {1, 2, ..., K}, oricare ar fi K < N.
De exemplu, pentru N=3, permutarea {2, 1, 3} nu îndeplineşte condiţia cerută, deoarece pentru K=2, {2,1} este o permutare pentru {1,2}, permutarea {1,3,2} nu o îndeplineşte pentru că {1} este permutare a mulţimii {1}, pe când permutările {2,3,1}, {3, 1, 2}, {3, 2, 1} o îndeplinesc.
Cerinţă
Scrieţi un program care să determine numărul permutărilor mulţimii {1, 2, ..., N} care îndeplinesc condiţia cerută. Pentru că acest număr poate fi foarte mare, se va determina acest număr modulo 997.
Date de intrare
Fişierul de intrare permutari.in
conţine pe prima linie numărul natural N.
Date de ieşire
Fişierul de ieşire permutari.out
va conţine un singur număr natural reprezentând numărul modulo 997 al permutărilor mulţimii {1, 2, ..., N} care îndeplinesc condiţia cerută.