과거 문제 공유

JAG 대학 ICPC 학과에는 $N$명의 학생이 있으며, 각 학생에게는 1부터 $N$까지 번호가 붙어 있다. 또 학생들 사이에 교우 관계가 $M$개 있다. $i$번째 교우 관계는 학생 $a_i$와 $b_i$가 친구이며 서로 연락할 수 있음을 나타낸다.

학과 기말고사에서는 $N$개 교과의 시험이 치러질 예정이다. 처음에 학생 $i$는 교과 $i$의 과거 문제를 가지고 있다. 당신은 학생 1이다. 친구끼리 과거 문제를 공유하는 일을 반복했을 때, 당신이 몇 개 교과의 과거 문제 정보를 얻게 되는지 알고 싶다. 그래서 친구끼리 과거 문제를 $K$번 공유했을 때의 기댓값을 구하기로 했다.

다음 이벤트가 독립적으로 순서대로 $K$번 일어난다고 하자.

• $M$개의 교우 관계 중 하나를 무작위로 고르고, 그 관계의 두 학생이 연락한다. 이때 각자가 가진 과거 문제 정보를 모두 공유한다.
  • 달리 말해, 한쪽이 가진 교과 집합을 $X$, 다른 쪽을 $Y$라고 하면, 이벤트 후 두 학생이 가진 교과 집합은 모두 $X \cup Y$가 된다.

$K$번의 이벤트가 끝난 뒤, 학생 1인 당신이 가진 과거 문제의 교과 수의 기댓값을 998244353으로 나눈 나머지로 구하라.

이 문제에서 구하는 기댓값은 반드시 유리수가 된다는 것을 증명할 수 있다. 또한 이 문제의 제약 아래에서는 그 값을 기약분수 $P/Q$로 나타냈을 때 $Q \not\equiv 0 \pmod{998244353}$이 됨을 증명할 수 있다. 따라서 $R \times Q \equiv P \pmod{998244353}$, $0 \le R < 998244353$을 만족하는 정수 $R$이 하나로 정해진다. 이 $R$이 기댓값을 998244353으로 나눈 나머지이다. 여기서 $998244353 = 2^{23} \times 7 \times 17 + 1$은 소수이다.

입력은 여러 데이터셋으로 이루어진다. 데이터셋의 개수는 50을 넘지 않는다. 각 데이터셋은 다음 형식으로 주어진다.

$N$ $M$ $K$

$a_1$ $b_1$

$\vdots$

$a_M$ $b_M$

첫 줄에는 $N$, $M$, $K$가 주어진다. $N$은 학생 수이며 2 이상 10 이하의 정수이다. $M$은 교우 관계의 수이며 1 이상 $N(N-1)/2$ 이하의 정수이다. $K$는 이벤트가 일어나는 횟수이며 1 이상 50 이하의 정수이다.

이어지는 $M$개의 줄에는 교우 관계 정보가 주어진다. $i$번째 줄에는 $a_i$와 $b_i$가 주어지며, 둘 다 1 이상 $N$ 이하의 정수이다. 자기 자신과의 교우 관계는 주어지지 않는다. 즉 모든 $1 \le i \le M$에 대해 $a_i \ne b_i$이다. 같은 교우 관계가 여러 번 주어지지 않는다. 즉 $i \ne j$이면 $\{a_i, b_i\} \ne \{a_j, b_j\}$이다.

입력의 끝은 0이 세 개 있는 줄로 표시된다.

각 데이터셋에 대해 답을 한 줄에 출력하라.