Pe un cerc sunt <tex>2n</tex> puncte distincte numerotate în ordinea acelor ceasornicului de la <tex>1</tex> la <tex>2n</tex> ( <tex>1, 2, 3, \ldots, 2n-1, 2n</tex> ). Punctele se unesc două câte două prin segmente de dreaptă, astfel ca unei perechi de numere să-i corespundă o coardă a cercului. Fiecare număr este conectat la exact un alt număr şi nu e permis ca două coarde să se intersecteze.

Scrieţi un pogram care să calculeze în câte moduri distincte se pot conecta cele <tex>2n</tex> numere (puncte) de pe cerc astfel încât coardele să nu se intersecteze.

Scrieţi un pogram care să calculeze **în câte moduri distincte** se pot conecta cele <tex>2n</tex> numere (puncte) de pe cerc astfel încât coardele să nu se intersecteze.

h2. Date de intrare

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

Fişierul de intrare $coarde.in$ conţine mai multe exemple de test. Un exemplu conţine pe o singură linie un întreg <tex>n</tex> pentru care trebuie să se determine numărul coardelor formate de cele <tex>2n</tex> puncte de pe cerc. Fişierul se termină cu o linie conţinând un **0**.

h2. Date de ieşire

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

Fişierul de ieşire $coarde.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 moduri distincte** luat modulo **9999991**, în care pot fi unite punctele cercului astfel încât coardele să nu se intersecteze.

h2. Restricţii

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

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

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

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

| 2
  3
  0
| 1:2
  2:5

|

h3. Explicaţie
 
...
 

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