Qrafiklərin hesablanması

Besinin n zirvəsi və m qırağı olan əlaqəli istiqamətsiz qrafı G var. G özünə döngələr (zirvədən özünə qayıdan qıraqlar) ehtiva edə bilər, lakin paralel qıraqları (eyni son nöqtələri birləşdirən bir neçə qıraq) yoxdur.

fG(a, b) funksiyası, 1 ≤ a ≤ n və 0 ≤ b üçün, zirvə 1-dən zirvə a-ya qədər tam olaraq b qıraq keçərək yol varsa doğru, əks halda yalan cavab verir. Əgər qıraq bir neçə dəfə keçilirsə, bu say cavaba daxil edilir.

Elza Besini təqlid etmək istəyir. Xüsusilə, o, elə bir istiqamətsiz qraf G′ qurmaq istəyir ki, fG′(a, b) = fG(a, b) bütün a və b üçün doğru olsun.

Sizin vəzifəniz Elzanın yarada biləcəyi müxtəlif G′ qraflarının sayını 10^9 + 7 modulunda hesablamaqdır. G kimi, G′ döngələr ehtiva edə bilər, lakin paralel qıraqları ola bilməz (bu, n zirvəli qrafların cəmi 2 ^ ((n^2 + n) / 2) olduğunu göstərir).

Hər bir giriş t testdən ibarətdir, bunlar müstəqil həll edilməlidir. n^2 cəminin bütün testlər üzrə 10^5-i keçməyəcəyi təmin edilir.

Giriş məlumatları

Girişin ilk sətiri testlərin sayını t (1 ≤ t ≤ 10^5 / 4) ehtiva edir.

Hər bir testin ilk sətiri iki tam ədəd n və m (1 ≤ n ≤ 10^2, n − 1 ≤ m ≤ (n^2 + n) / 2) ehtiva edir.

Hər bir testin növbəti m sətiri G-də x və y zirvələrini birləşdirən qırağı göstərən iki tam ədəd x və y (1 ≤ x ≤ y ≤ n) ehtiva edir.

Ardışıq testlər oxunaqlılığı artırmaq üçün boş sətirlə ayrılır.

Çıxış məlumatları

Hər bir test üçün yeni sətirdə müxtəlif G′ qraflarının sayını 10^9 + 7 modulunda çıxarın.

Nümunə

Bu testdə G′ ya G-yə bərabər ola bilər, ya da aşağıdakı iki qrafdan biri ola bilər:

5 4
1 2
1 4
3 4
3 5
5 5
1 2
2 3
1 4
3 4
3 5