F. Ursa Minor

小熊座是一個坐落於北半球星空的星座。與北斗七星類似，小熊座一共有七顆星星，形成了勺子一樣的結構。

勾陳一，又稱為小熊座 ，是小熊座中最明亮的星星，同時也是現在天空的北極星.

給你一個 個點 條邊的無向圖，每個點代表一顆星星，保證無向圖不存在自環或重邊。點的編號為 ，其中勾陳一是第 個點。

小明想找出這個圖裡有多少種情況可以形成小熊座那樣的結構（選擇另外六個點與 號點形成圖片中的子圖）。但這個問題太難了，於是他稍加了一點限制：

具體地，小明想要找到有多少個有序六元組 滿足：

• 在無向圖中存在邊 和 ；
• 對於所有的 ，圖中不存在邊 ；
• 對於所有的 ，滿足 ；
• 對於所有的 ，滿足 。

答案可能很大，你只需要輸出答案對 取模後的結果。

Ursa Minor, also known as the Little Bear, is a constellation located in the far northern sky. There are seven stars in the Little Bear, with four of them in its bowl, like Big Dipper.

Polaris, the brightest one in the constellation, is also known as North Star.

You are given an undirected graph with stars and edges. It is guaranteed that the graph has no self-circle or multiple edges. The stars are numbered from to , and Polaris is the -th star.

Alice wants to count the number of Ursa Minors in this graph(pick out another six stars and form a subgraph just like the above picture). But that is too hard for her, so she adds a single constraint:

Specifically, she wants to find out how many tuples of six different stars such that:

• the graph contains edges and .
• the graph does not contain edges for all .
• for all .
• for all .

Since the answer may be large, print the answer modulo .

第一行一個整數 ，表示數組組數。

對於每組數據：

第一行三個整數 ，分別表示星星的個數、邊數與勾陳一的編號。

接下來 行，其中每行兩個整數 ，表示圖中的一條邊。數據保證不存在重邊或自環。

The first line contains a single integer , denoting the number of test cases.

For each test case:

The first line contains three integers , denoting the number of stars, the number of edges and the index of Polaris respectively.

For the next lines, each line contains two integers , denoting an edge in the graph. It is guaranteed that and the graph has no self-circle or multiple edges.

對於每組數據，輸出答案對 取模後的結果。

For each test case, print a single integer denoting the answer modulo .

Sample input

2
7 7 7
1 2
2 3
3 4
4 1
4 5
5 6
6 7
10 15 7
1 2
2 3
3 4
1 4
4 5
5 6
6 7
5 8
7 8
9 4
9 5
9 8
10 4
10 5
10 8

Sample output

1
4

對於全部測試數據，滿足 。

It is guaranteed that .