Problem H

Problem H
Graph Coloring in HSL

Input: Standard Input

Output: Standard Output

Most of you must know about RGB color model, where, each color is described via three color components, red, green and blue. HSL(Hue, Saturation, Lightness) is another type of color model, where each color is described by three values, hue, saturation and lightness. It is presented in a cylindrical structure.


Figure 1: HSL Model	Figure 2: Cross section (at lightness = 0.5) (Those who are using a printed copy of the statement may not see the actual colour, but you will surely notice the change of grey shade)

Figure 1 demonstrates the HSL model. The angle around the central vertical axis is hue, the distance from the axis is saturation, and the distance along the axis corresponds to lightness.

The basic idea behind HSL is, it starts at hue = 0° at red, passing through green at 120° and blue at 240° and wrapping to red again at 360°. A cross section of the model is shown in figure 2.

In this problem, you have to color a graph with at most P colors, where P is a prime number. Each color has same same saturation and lightness, and their hue is evenly distributed starting at 0° (that is if 3 colors are used, hue will be 0°, 120°, 240°).

Given a graph G=(V,E), you have to color all vertices v є V, such that color of a node is equal to the sum of color of it's neighbours. Since, all colors have same lightness and saturation, they are ignored.

Find the number of ways to colour the graph. Two colorings are considered different, if there is at least one vertex, that has different color in the two colorings.

Input

First line of input contains an integer T(T<=400), the number of test cases.

This is followed by three integers N,M and P (1 £ N £ 100, 2 £ P £ 1000000000, P is a prime), the number of vertices, the number of edges, and the number of colors. All the colors have same saturation, lightness, and i^th color has hue of i*(360/P) degree. P is a prime number.

Next M lines each contain two integers, p_i and q_i, denoting that p_i and q_i are neighbours (1£p_i,q_i£N). The graph is bidirectional. All vertices are identified by a number between 1 and N. There will be no self loops. All edges will be listed exactly once.

Output

For each test case, output the number of solutions. This number can be very large. Output it modulo 1000000007.

Sample Input Output for Sample Input

5 4 3

1 2

1 3

2 4

3 5

3 0 3

Case 1: 3

Case 2: 1

Description of the Sample Case 1

There are 3 colors. So, the hue of them will be 0°, 120°, 240°. Let us assume that, black represents color with hue 0°, grey with 120° and white with 240°.


Original Graph

Reference: Description and illustration of HSL model is taken from wikipedia.
http://en.wikipedia.org/wiki/HSL_and_HSV

Problemsetter: Manzurur Rahman Khan

Special Thanks to: Mohammad Mahmudur Rahman