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

h3. Explicaţie

Pentru primul exemplu:
 

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