약속한 시각에 만나기

앨리스와 밥은 교차로가 $N$개인 도시에 산다. 교차로에는 1번부터 $N$번까지 번호가 붙어 있다. 도로는 $M$개이고, 각 도로는 양방향이며 서로 다른 두 교차로를 직접 잇는다. 두 교차로를 잇는 도로는 많아야 하나다.

앨리스의 집은 1번 교차로에, 밥의 집은 $N$번 교차로에 있다. 두 사람은 낮 12시에 각자의 집을 나서 도시를 돌아다닌다. 1분마다 두 사람 모두 지금 서 있는 교차로에서 도로로 직접 이어진 다른 교차로로 옮겨 간다. 제자리에 머무르는 것은 허용하지 않으므로 매 분 반드시 한 번씩 움직인다.

두 사람은 12시에서 정확히 $T$분 뒤에 어느 교차로에서 만나기로 했고, 그 전에는 서로 마주치고 싶지 않다. 즉 0분부터 $T-1$분까지는 항상 서로 다른 교차로에 있어야 하고, $T$분에는 같은 교차로에 있어야 한다. 두 사람이 워낙 빠르게 움직여서 같은 도로를 서로 반대 방향으로 지나치는 것은 마주친 것으로 치지 않는다.

두 사람이 도시를 돌아다니는 방법이 몇 가지인지 구하여라. 앨리스가 지나는 교차로의 순서나 밥이 지나는 교차로의 순서 중 하나라도 다르면 서로 다른 방법이다.

첫째 줄에 테스트 케이스의 개수 $K$가 주어진다 ($1 \le K \le 5$). 이어서 $K$개의 테스트 케이스가 아래 형식으로 주어진다.

각 테스트 케이스의 첫째 줄에는 정수 $N$, $M$, $T$가 주어진다 ($2 \le N \le 10$, $1 \le M \le 50$, $1 \le T \le 10^{12}$). 다음 $M$개의 줄에는 도로 정보가 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $A$와 $B$가 주어지고, $A$번 교차로와 $B$번 교차로를 잇는 양방향 도로가 있다는 뜻이다 ($1 \le A \le N$, $1 \le B \le N$, $A \ne B$).

각 테스트 케이스마다 앨리스와 밥이 $T$분에 같은 교차로에 있고 그 전에는 한 번도 같은 교차로에 있지 않도록 움직이는 방법의 수를 9973으로 나눈 나머지를 한 줄에 하나씩 출력한다.