Meeting at the Agreed Minute

Alice and Bob live in a city with $N$ intersections, numbered 1 through $N$. The city has $M$ roads. Every road is bidirectional and joins two different intersections directly, and each pair of intersections is joined by at most one road.

Alice lives at intersection 1 and Bob lives at intersection $N$. At noon they leave their houses and start wandering through the city. Every minute each of them moves from the intersection they are standing on to another intersection joined to it by a road. Staying in place is not allowed, so each of them moves exactly once per minute.

They agree to meet at some intersection exactly $T$ minutes after noon, and they do not want to run into each other before then. That is, at every minute from 0 to $T-1$ the two stand at different intersections, and at minute $T$ they stand at the same intersection. They travel fast, so passing each other on one road in opposite directions does not count as running into each other.

Count the ways the two can move through the city. Two ways differ if Alice's sequence of intersections differs, or Bob's does.

The first line contains an integer $K$, the number of test cases ($1 \le K \le 5$). Then $K$ test cases follow in the format below.

The first line of each test case contains three integers $N$, $M$ and $T$ ($2 \le N \le 10$, $1 \le M \le 50$, $1 \le T \le 10^{12}$). Each of the next $M$ lines contains two integers $A$ and $B$, meaning that a bidirectional road joins intersection $A$ and intersection $B$ ($1 \le A \le N$, $1 \le B \le N$, $A \ne B$).

For each test case, print on one line the number of ways Alice and Bob can move so that they stand at the same intersection at minute $T$ and never stand at the same intersection before then, modulo 9973.