AT_abc294_h [ABC294Ex] K-Coloring

[problemUrl]: https://atcoder.jp/contests/abc294/tasks/abc294_h 頂点に $ 1 $ から $ N $ の、辺に $ 1 $ から $ M $ の番号がついた $ N $ 頂点 $ M $ 辺の単純無向グラフが与えられます。辺 $ i $ は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 このグラフのそれぞれの頂点に $ 1 $ 以上 $ K $ 以下の整数を書きこむ方法のうち、次の条件を満たす方法の個数を $ 998244353 $ で割った余りを求めてください。 - 辺で結ばれた頂点同士には異なる数が書きこまれている。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

条件を満たすように頂点に $ 1 $ 以上 $ K $ 以下の整数を書きこむ方法の個数を $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 30 $ - $ 0\ \leq\ M\ \leq\ \min\ \left(30,\ \frac{N(N-1)}{2}\ \right) $ - $ 1\ \leq\ K\ \leq\ 10^9 $ - $ 1\ \leq\ u_i\ \lt\ v_i\ \leq\ N $ - 入力で与えられるグラフは単純 ### Sample Explanation 1 条件を満たす整数の書きこみ方は次の $ 2 $ 通りです。 - 頂点 $ 1,\ 3,\ 4 $ に $ 1 $ を、頂点 $ 2 $ に $ 2 $ を書きこむ。 - 頂点 $ 2 $ に $ 1 $ を、頂点 $ 1,\ 3,\ 4 $ に $ 2 $ を書きこむ。 ### Sample Explanation 2 $ 10^4 $ 通り全ての書きこみ方が条件を満たします。