Sharing Past Exam Notes

At the JAG University ICPC department, there are $N$ students, numbered from 1 to $N$. There are $M$ friendships among them. The $i$-th friendship means that students $a_i$ and $b_i$ are friends and can contact each other.

The department's final exams will cover $N$ subjects. Initially, student $i$ has the past exam papers for subject $i$. You are student 1. You want to know how many subjects' past exam information you end up with after friends repeatedly share past exams. So you want the expected value after $K$ sharing events between friends.

Consider the following event, which happens $K$ times in order, independently.

• One of the $M$ friendships is chosen at random, and the two students in it contact each other. They then share all the past exam information they have.
  • In other words, if the set of subjects one student has is $X$ and the other's is $Y$, then after the event both students have the set $X \cup Y$.

After the $K$ events, find the expected number of subjects whose past exam papers you (student 1) have, modulo 998244353.

The expected value is always a rational number. It can be proven that under the constraints of this problem, when written as an irreducible fraction $P/Q$, $Q \not\equiv 0 \pmod{998244353}$. Therefore, there is a unique integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}$ and $0 \le R < 998244353$. This $R$ is the expected value modulo 998244353. Here, $998244353 = 2^{23} \times 7 \times 17 + 1$ is prime.

The input consists of multiple datasets. The number of datasets is at most 50. Each dataset is given in the following format.

$N$ $M$ $K$

$a_1$ $b_1$

$\vdots$

$a_M$ $b_M$

The first line gives $N$, $M$, and $K$. $N$ is the number of students, an integer from $2$ to $10$. $M$ is the number of friendships, an integer from $1$ to $N(N-1)/2$. $K$ is the number of events, an integer from $1$ to $50$.

The next $M$ lines give the friendships. The $i$-th line gives $a_i$ and $b_i$, each an integer from $1$ to $N$. No friendship connects a student to themselves, so $a_i \ne b_i$ for all $1 \le i \le M$. No friendship is given more than once, so for $i \ne j$, $\{a_i, b_i\} \ne \{a_j, b_j\}$.

The input ends with a line containing three zeros.

For each dataset, print the answer on one line.