AlgoLiga 2018

W Bajtocji wybudowano sieć szybkich dróg łączących wszystkie miasta w kraju. Teraz pora na opracowanie systemu opłat za korzystanie z nich.

Wszystkie miasta ponumerowano kolejnymi liczbami od 1 do N. Stolica kraju otrzymała nr 1. Dróg wybudowano N-1 w taki sposób, że można przejechać z dowolnego miasta do każdego innego. Dokładniej, jeśli miasto (oprócz stolicy) ma numer n, to jest połączone nową drogą z miastem o numerze d takim, że d jest największym dzielnikiem właściwym n, więc pary połączonych miast to: 2-1, 3-1, 4-2, 5-1, 6-3, 7-1, 8-4, 9-3, 10-5,... itd.

Król Bajtazar pozwolił, aby za przejazd każdą drogą pobierać opłatę, która po równo będzie zasilała budżety połączonych nią miast. Warunek jest tylko taki, aby opłata wyrażała się całkowitą nieujemną liczbą bajtalarów i nie była większa od pewnej nieparzystej wartości M, którą król ustali. Dodatkowo, doradcy króla zasugerowali, aby narzucić szereg warunków dotyczących tego, czy suma opłat za przejazd pomiędzy wybranymi miastami będzie parzysta czy nieparzysta.

Bajtazar chciałby wiedzieć na ile sposobów można opracować system opłat, uwzględniający postawione warunki. Ponieważ liczba ta może być bardzo duża, wystarczy podać resztę z dzielenia jej przez 1000000007.

Wejście

W pierwszej linii liczba testów t (t ≤ 10).

W pierwszej linii każdego testu trzy liczby całkowite N, M, W oznaczające odpowiednio: liczbę miast (2 ≤ N ≤ 10⁶), maksymalną opłatę za przejazd drogą (1 ≤ M < 10⁹, 2 ∤ M) i liczbę par miast, dla których określono warunek dotyczący sumy opłat za przejazd pomiędzy nimi (0 ≤ W ≤ 10⁵).

W kolejnych W liniach, po trzy liczby całkowite a, b i p, gdzie a i b to numery wybranych miast (1 ≤ a, b ≤ N, a ≠ b), a p oznacza, czy suma opłat za przejazd pomiędzy tymi miastami musi być parzysta (p=0) czy nieparzysta (p=1).

Wyjście

Dla każdego testu, w osobnej linii, liczba możliwych taryf (rozumianych jako zbiór wyznaczonych opłat za przejazd poszczególnymi drogami) modulo 1000000007.

Przykład

Wejście:
2
3 1 1
2 3 1
4 3 2
1 4 0
3 2 1

Wyjście:
2
16

Pomoc do przykładu: 
W drugim teście są cztery miasta, więc trzy drogi: 2-1, 3-1, 4-2. Przyjmując taką kolejność stawek opłat w taryfie, mamy następujące możliwości: (0,1,0), (0,1,2), (0,3,0), (0,3,2), (1,0,1), (1,0,3), (1,2,1), (1,2,3), (2,1,0), (2,1,2), (2,3,0), (2,3,2), (3,0,1), (3,0,3), (3,2,1), (3,2,3).