AT_abc327_g [ABC327G] Many Good Tuple Problems

[problemUrl]: https://atcoder.jp/contests/abc327/tasks/abc327_g > この問題における良い数列の組の定義は D 問題と同じです。 $ N $ 以下の正整数からなる長さ $ M $ の数列の組 $ (S,\ T)\ =\ ((S_1,\ S_2,\ \dots,\ S_M),\ (T_1,\ T_2,\ \dots,\ T_M)) $ が **良い数列の組である** とは、$ (S,\ T) $ が次の条件を満たすことを言います。 - $ 0,1 $ からなる長さ $ N $ の数列 $ X\ =\ (X_1,\ X_2,\ \dots,\ X_N) $ であって次の条件を満たすものが存在する。 - $ i=1,\ 2,\ \dots,\ M $ それぞれについて、$ X_{S_i}\ \neq\ X_{T_i} $ が成立する。 $ N $ 以下の正整数からなる長さ $ M $ の数列の組 $ (A,\ B)\ =\ ((A_1,\ A_2,\ \dots,\ A_M),\ (B_1,\ B_2,\ \dots,\ B_M)) $ としてあり得るものは $ N^{2M} $ 通りありますが、そのような数列の組のうち良い数列の組であるものの個数を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $

$ N $ 以下の正整数からなる長さ $ M $ の数列の組のうち、良い数列の組であるものの個数を $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 30 $ - $ 1\ \leq\ M\ \leq\ 10^9 $ - $ N,\ M $ は整数 ### Sample Explanation 1 例えば $ A=(1,2),\ B=(2,3) $ のとき $ (A,\ B) $ は良い数列の組です。$ X=(0,1,0) $ とすると、$ X $ は $ 0,1 $ からなる長さ $ N $ の数列で、 $ X_{A_1}\ \neq\ X_{B_1} $ かつ $ X_{A_2}\ \neq\ X_{B_2} $ を満たします。よって、$ (A,B) $ は良い数列の組としての条件を満たしています。 良い数列の組は全部で $ 36 $ 個あるので、これを出力します。