== include(page="template/taskheader" task_id="arbori2") ==

Se consideră **toţi arborii binari de căutare distincţi** având <tex>n</tex> noduri, cu cheile nodurilor de la <tex>1</tex> la <tex>n</tex> şi care au secvenţa de traversare **INordine**: <tex>1 \: 2 \: 3 \: \ldots \: n</tex>. Se ordonează arborii de mai sus în **ordinea lexicografică descrescătoare** a secvenţelor de traversare **PREordine**. De exemplu pentru <tex>n=4</tex> avem arborii de mai jos:

Se consideră toţi arborii binari de căutare distincţi având <tex>n</tex> noduri, cu cheile nodurilor de la <tex>1</tex> la <tex>n</tex> şi care au secvenţa de traversare INordine: <tex>1 2 3 \ldots n</tex>. Se ordonează arborii de mai sus în ordinea lexicografică  descrescătoare a secvenţelor de traversare PREordine. De exemplu pentru <tex>n=4</tex> avem arborii de mai jos:

!problema/arbori2?arbori2.png!

Se observă că toţi cei **14 arbori distincţi** au secvenţa de traversare INordine <tex>1 \: 2 \: 3 \: 4</tex> iar secvenţele de traversare **PREordine** sunt în **ordine lexicografică descrescatoare**.
 
Fiind dată **secvenţa de traversare PREordine** a unui **arbore de căutare definit mai sus** se cere să se calculeze **numărul de ordine** al arborelui.
 

h2. Date de intrare

Fişierul de intrare $arbori2.in$ conţine mai multe exemple de test. Un exemplu are pe prima linie un întreg <tex>n</tex> precizând numărul nodurilor arborelui binar de căutare (având cheile <tex>1, 2, 3, \ldots, n</tex> şi secventa de traversare **INordine** <tex>1 \: 2 \: 3 \: \ldots \: n</tex>). Pe linia următoare sunt <tex>n</tex> întregi separaţi de un spaţiu  reprezentând secvenţa cheilor obţinuta la traversarea **PREordine** a arborelui binar de căutare. Fişierul se termină cu o linie conţinând un **0**.

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

h2. Date de ieşire

Fişierul de ieşire $arbori2.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 ordine**, luat modulo **9999991**, al arborelui binar de căutare cu secvenţa cheilor la traversarea **PREordine** dată.

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

h2. Restricţii

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

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

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

| 4
  3 1 2 4
  30
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  0
| 1:7
  2:5583241

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

|

h2. Precizări
 
Un arbore binar de căutare este un arbore binar ce satisface următoarele condiţii:
 
* subarborele stâng al unui nod conţine numai noduri cu chei mai mici decât cheia nodului
* subarborele drept al unui nod conţine numai noduri cu chei mai mari decât cheia nodului
* atât subarborele stâng al unui nod, cât şi cel drept sunt arbori binari de căutare
 
!problema/arbori2?arbore_ex.png!
 
O traversare PREordine (Rădacină-Stânga-Dreapta) a arborelui tipăreşte cheia rădăcinii urmată de traversarea subarborelui stâng şi apoi a celui drept. O traversare INordine (Stânga-Rădacină-Dreapta) a arborelui tipăreşte subarborele stâng, apoi tipăreşte cheia rădăcinii şi la sfârşit subarborele drept. De exemplu traversarea arborelui de mai sus este:
 
* PREordine: <tex>6 \: 4 \: 2 \: 1 \: 3 \: 5 \: 9 \: 7 \: 8</tex>
* INordine: <tex>1 \: 2 \: 3 \: 4 \: 5 \: 6 \: 7 \: 8 \: 9</tex>
 
 
Două secvenţe de numere <tex>X_1, X_2, \ldots, X_n</tex> şi <tex>Y_1, Y_2, \ldots, Y_n</tex> sunt ordonate lexicographic descrescător dacă:
 
* <tex>X_1 > Y_1</tex> sau
* <tex>X_1 = Y_1</tex> şi <tex>X_2 > Y_2</tex> sau
* <tex>X_1 = Y_1</tex> şi <tex>X_2 = Y_2</tex> şi <tex>X_3 > Y_3</tex> sau
* <tex>\ldots</tex>
* <tex>X_1 = Y_1</tex> şi <tex>X_2 = Y_2</tex> şi <tex>\ldots</tex> <tex>X_{n-1} = Y_{n-1}</tex> şi <tex>X_n > Y_n</tex>

h3. Explicaţie
...

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