Cerința

În judeţul lui Dorel sunt n localităţi legate între ele prin m drumuri. Dorel e interesat să afle în câte moduri se pot alege n-1 drumuri din cele m date, astfel încât folosind aceste drumuri să se poată ajunge de la orice localitate la oricare alta.

Date de intrare

Fișierul de intrare arbori_in_graf.in conține pe prima linie numerele n şi m, iar pe următoarele m linii câte o pereche de numere distincte de la 1 la n, reprezentând două localităţi între care există drum.

Date de ieșire

Fișierul de ieșire arbori_in_graf.out va conține pe prima linie numărul de moduri cerut, modulo 1.000.000.007.

Restricții și precizări

• 2 ≤ n ≤ 50
• 0 ≤ m ≤ n(n-1)/2

Exemplu:

arbori_in_graf.in

2 1
1 2 

arbori_in_graf.out

1

Explicație

Graful dat este arbore.

Vezi teorema lui Kirchhoff