010 - 過去問の共有

問題

HOJ 大学 Monja 学科には N 人の学生が在籍しており，それぞれの学生には 1 から N までの番号がついている．また，学生の交友関係が M 個存在する． i 番目の交友関係は，学生 a _i と b _i が友達であり，互いに連絡できることを表す．

学科の期末試験では， 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 = 2 ²³ × 7 × 17 + 1 は素数である．

Input

入力は複数のデータセットからなる．データセットの個数は 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 番目の行には a _i および b _i が与えられ，それぞれ 1 以上 N 以下の整数である．自分自身に交友関係があるような入力は与えられない．すなわち，すべての 1 ≤ i ≤ M について a _i ≠ b _i を満たす．また，同じ交友関係が複数与えられることはない．すなわち，すべての 1 ≤ i, j ≤ M について， i ≠ j ならば { a _i , b _i } ≠ { a _j , b _j } を満たす．

入力の終わりは 3 つのゼロからなる行で表される．

Output

各データセットについて，答えを 1 行で出力せよ．

Sample Input

4 3 2
1 2
1 4
3 4
4 3 9
2 3
2 4
3 4
10 20 30
3 5
6 4
1 6
1 8
7 2
9 3
2 3
6 10
1 9
3 10
2 8
4 10
5 1
7 3
10 8
4 9
3 8
10 1
5 9
4 5
0 0 0

Sample Output

887328316
1
369808863