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