過去問の共有
시간 제한8초메모리 제한1024 MB
K번의 단계마다 무작위로 간선 하나를 골라 두 학생의 기출문제 집합을 합칠 때, 학생 1이 가지게 되는 과목 수의 기대값을 998244353으로 나눈 나머지로 구한다.
문제
JAG 大学 ICPC 学科には N 人の学生が在籍しており，それぞれの学生には 1 から N までの番号がついている．また，学生の交友関係が M 個存在する．i 番目の交友関係は，学生 ai と bi が友達であり，互いに連絡できることを表す．
学科の期末試験では，N 教科の試験が行われる予定である．はじめ，学生 i は教科 i の過去問を持っている． あなたは学生 1 である．友達同士で過去問を共有することを繰り返したとき，あなたが過去問の情報を何教科得られるかが気になった．そこで，友達同士で行われる過去問の共有が K 回行われたときの期待値を調べることにした．
次のイベントが順に K 回独立に発生することを考える．
- M 個の交友関係のうち一つがランダムに選ばれ，その学生二人が連絡を取りあう．このとき，それぞれが持つ過去問情報をすべて共有しあう．
- 言い換えると，片方が持つ過去問の教科の集合を X，もう片方を Y とすると，そのイベントの後，持っている過去問の教科の集合は双方とも X ∪ Y になる．
K 回のイベントの終了後，学生 1 であるあなたが持っている過去問の教科数の期待値を mod 998244353 で求めよ．
なお，この問題において，求める期待値は必ず有理数になることが証明できる．また，この問題の制約のもとでは，その値を既約分数 P/Q で表したとき，Q ≢ 0 (mod 998244353) となることも証明できる．よって，R × Q ≡ P (mod 998244353), 0 ≤ R < 998244353 を満たす整数 R が一意に定まる．この R が，期待値 mod 998244353 である．ここで，998244353 = 223 × 7 × 17 + 1 は素数である．
입력
入力は複数のデータセットからなる．データセットの個数は 50 を超えない．各データセットは次の形式で表される．
N M K
a1 b1
⋮
aM bM
1 行目には N，M および K が与えられる．N は学生の人数であり，2 以上 10 以下の整数である．M は交友関係の個数であり，1 以上 N(N-1)/2 以下の整数である．K はイベントが発生する回数であり，1 以上 50 以下の整数である．
続く M 行には，交友関係の情報が与えられる．このうち i 番目の行には ai および bi が与えられ，それぞれ 1 以上 N 以下の整数である．自分自身に交友関係があるような入力は与えられない．すなわち，すべての 1 ≤ i ≤ M について ai ≠ bi を満たす．また，同じ交友関係が複数与えられることはない．すなわち，すべての 1 ≤ i, j ≤ M について，i ≠ j ならば { ai, bi } ≠ { aj, bj } を満たす．
入力の終わりは 3 つのゼロからなる行で表される．
출력
各データセットについて，答えを 1 行で出力せよ．