32092번 - 過去問の共有 다국어

문제

JAG 大学 ICPC 学科には 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 は素数である.

입력

入力は複数のデータセットからなる.データセットの個数は 50 を超えない.各データセットは次の形式で表される.

N M K

a₁ b₁

⋮

a_M b_M

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 つのゼロからなる行で表される.

출력

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

제한

힌트