Se dă un arbore având <tex>n</tex> noduri numerotate <tex>1, 2, \ldots, n</tex> ale cărui <tex>n-1</tex> arce au ataşate ca lungimi numere întregi. Se consideră cele <tex>n!</tex> permutări ale elementelor mulţimii <tex>\lbrace 1, 2, \ldots, n \rbrace</tex> notate cu <tex>P_i</tex>, unde <tex>1 \leq i \leq n!</tex>. De asemenea notăm cu <tex>P_{i,j}</tex> al <tex>j</tex>-lea element al mulţimii <tex>P_i</tex> (<tex>1 \leq j \leq n</tex>).

Fiecare permutare <tex>P_i</tex> reprezintă o traversare a secvenţei de noduri ale arborelui ceea ce înseamnă că ne deplasăm de la nodul <tex>P_{i,1}</tex> la nodul <tex>P_{i,2}</tex> pe drumul cel mai scurt, pe urmă de la nodul <tex>P_{i,2}</tex> la nodul <tex>P_{i,3}</tex> tot pe drumul cel mai scurt şi tot aşa până la nodul <tex>P_{i,n}</tex>. Notăm distanţa totală a traversării date de permutarea <tex>P_i</tex> cu <tex>D(P_i)</tex>.
 
Se cere să se calculeze suma distanţelor <tex>D(P_i)</tex> pentru toate cele <tex>n!</tex> permutări.
 

h2. Date de intrare

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

Fişierul de intrare $arbori3.in$ conţine mai multe exemple de test. Un exemplu are o linie conţinând un singur număr natural <tex>n</tex>, urmată de <tex>n-1</tex> linii conţinând fiecare trei întregi <tex>X</tex>, <tex>Y</tex> şi <tex>L</tex> separaţi de un spaţiu şi reprezentând un arc al arborelui între nodurile <tex>X</tex> şi <tex>Y</tex>, având lungimea <tex>L</tex>. Fişierul se termină cu o linie conţinând un singur 0.

h2. Date de ieşire

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

Fişierul de ieşire $arbori3.out$ conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte suma distanţelor <tex>D(P_i)</tex> pentru toate cele <tex>n!</tex> permutări luată modulo **9999991**.

h2. Restricţii

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

* <tex>2 \leq n \leq 10^5</tex>
* <tex>1 \leq L \leq 10^6</tex>
* numărul de teste nu depăşeşte 20

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

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

| 3
1 2 1
1 3 2
0
| 24

|

h3. Explicaţie
 
...

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