tenerife

Tenerife

h2. Date de ieşire

În fişierul de ieşire $tenerife.out$ se va afisa numarul de excursii diferite care au costul egal cu 1 modulo 1000000007.

În fişierul de ieşire $tenerife.out$ se va afisa numarul de excursii diferite care au costul egal cu $1$ modulo 1000000007.

h2. Restricţii

* 1 <= M <= 100.000
* 1 <= C, K <= 10^9^
* {*O excursie trebuie sa aiba minim 2 cluburi*}

* Pentru 10% din punctaj N <= 1000 si graful va avea forma de lant orientat intr-o singura parte.
* Pentru alte 10% din punctaj K = 1.
* Pentru alte 10% din punctaj K este numar prim.
* Pentru alte 20% din punctaj K <= 5000.
* Pentru alte 50% din punctaj restrictiile initiale.

* Pentru $10%$ din punctaj N <= 1000 si graful va avea forma de lant orientat intr-o singura parte.
* Pentru alte $10%$ din punctaj K = 1.
* Pentru alte $10%$ din punctaj K este numar prim.
* Pentru alte $20%$ din punctaj K <= 5000.
* Pentru alte $50%$ din punctaj restrictiile initiale.

h2. Exemplu

 5 6 7
 4 6 35
 7 5 15

| 12
|

| 12 |
| 10 12 840
1 2 2
1 3 10
2 3 6
3 4 15
4 5 10
5 6 25
6 7 35
7 8 50
8 9 20
9 10 49
1 9 42
4 6 200
| 33
|
 

h3. Explicaţie

Pentru primul exemplu:
 

Excursiile care au costul egal cu 1 sunt:
1) 3 -> 5
2) 5 -> 6