Se consideră elementele <tex>1, 2, \ldots, n</tex> şi permutările formate cu ele. Permutarea <tex>1, 2, \ldots, n</tex> se numeşte permutare principală. Se numeşte **substituţie de grad** <tex>n</tex> operaţia prin care se trece de la permutarea principală la o permutare dată. De exemplu pentru grad 10 avem substituţia:
<tex>\left(\begin{matrix}

    \pmb{1} & 2 & \pmb{3} & \pmb{4} & 5 & \pmb{6} & 7 & 8 &  9 & 10 \\
    \pmb{3} & 2 & \pmb{4} & \pmb{6} & 5 & \pmb{1} & 8 & 9 & 10 &  7
\end{matrix}\right)
\quad \text{ciclul lui 1} \rightarrow
\left(\begin{matrix}
    \pmb{1} & 3 &      4  & 6 \\
         3  & 4 & \pmb{6} & 1
\end{matrix}\right)
\quad \text{6 este maxim}
</tex>
 
Notăm cu <tex>s(i)</tex> elementul permutării care corespunde în permutarea principală elementului <tex>i</tex>. Pentru exemplul dat <tex>s(1)=3, s(2)=2, s(3)=4</tex>, etc. Se numeşte **substituţie circulară**, sau **ciclu**, o substituţie în care plecând de la elementul <tex>i</tex> şi aplicând succesiv operaţia  <tex>s()</tex> de <tex>p</tex> ori se ajunge din nou la elementul <tex>i</tex>. În exemplul de mai sus elementul 1 are un ciclu de 4 elemente: <tex>s(1)=3, s(3)=4, s(4)=6, s(6)=1</tex>. La fel elementul 7 are un ciclu de 4 elemente, iar elementele 2 şi 5 au un ciclu de 1 element. În ciclul elementului 1 avem elementul maxim al ciclului egal cu 6. Elementele ciclului <tex>1, 3, 4, 6</tex> din permutarea principală apar în permutarea substituţiei deplasate cu o poziţie la stânga <tex>3, 4, 6, 1</tex>. (Pentru substituţia: <tex>1, 6, 3, 4</tex> în permutarea principală ar fi <tex>6, 3, 4, 1</tex> în permutarea substituţiei.)
 
<tex>
\text{alt ciclu al lui 1} \rightarrow
\left(\begin{matrix}
    \pmb{1} & 6 & 3  & 4 \\
         6  & 3 & 4 & 1
\end{matrix}\right)
</tex>
sau respectand ordinea in permuarea principala
<tex>
\left(\begin{matrix}
    \pmb{1} & 2 & \pmb{3} & \pmb{4} & 5 & \pmb{6} & 7 &  8 & 9 & 10 \\
    \pmb{6} & 2 & \pmb{4} & \pmb{1} & 5 & \pmb{3} & 8 & 10 & 7 &  9
\end{matrix}\right)
\end{matrix}\right)
</tex>
 
Scrieţi un program care să calculeze **numărul permutărilor distincte** într-o substituţie de grad <tex>n</tex>, pentru care **elementul maxim** din **ciclul elementului 1** este de valoare <tex>k</tex>, unde <tex>1 \leq k \leq n</tex>.

    \pmb{1} & 2 & 3 & 4 & 5 & 6 & 7 & 8 &  9 & 10 \\
    \pmb{3} & 2 & 4 & 6 & 5 & 1 & 8 & 9 & 10 &  7
\end{matrix}\right)</tex>

h2. Date de intrare

Fişierul de intrare $substitutii.in$ conţine mai multe exemple de test. Un exemplu are pe o linie  doi întregi <tex>n</tex> şi <tex>k</tex> separaţi prin spaţiu determinând gradul <tex>n</tex> al substituţiei şi valoarea <tex>k</tex> a elementului maxim în ciclul elementului 1. Fişierul se termină cu o linie conţinând un 0.

Fişierul de intrare $substitutii.in$ ...

h2. Date de ieşire

Fişierul de ieşire $substitutii.out$ conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte numărul exemplului de test urmat de **':'** şi de **numărul de permutari distincte**, luat modulo **9999991**, pentru care **valoarea elementului maxim al ciclului lui 1** este cea specificată.

În fişierul de ieşire $substitutii.out$ ...

h2. Restricţii

* <tex>1 \leq n, k \leq 200</tex>

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. substitutii.in |_. substitutii.out |

|  2 1
   19 16
   0
| 1:1
  2:4476041

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="substitutii") ==