過去問の共有

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 行で出力せよ．