AT_abc321_g [ABC321G] Electric Circuit

[problemUrl]: https://atcoder.jp/contests/abc321/tasks/abc321_g $ 1 $ から $ N $ までの番号が付けられた $ N $ 個の部品と $ M $ 本のケーブルを使って電気回路を作ろうとしています。 これらの部品には赤い端子と青い端子がそれぞれ合計で $ M $ 個ずつ存在し、$ i $ 個目の赤い端子は部品 $ R_i $ に、$ i $ 個目の青い端子は部品 $ B_i $ についています。 各ケーブルは赤い端子 $ 1 $ つと青い端子 $ 1 $ つを繋ぎます。 特に、同じ部品についた $ 2 $ つの端子を繋ぐことも許されます。 また、$ 1 $ つの端子に対して $ 2 $ 本以上のケーブルを繋げることはできません。 したがって、$ M $ 本のケーブルの繋ぎ方は全部で $ M! $ 通りあります（ケーブル同士は区別しないことに注意してください）。 部品を頂点、ケーブルを辺としたグラフとしてこの回路を見たときの連結成分数を $ s $ とします。 $ M $ 本のケーブルの繋ぎ方を $ M! $ 通りからランダムに選ぶときの $ s $ の期待値を $ \text{mod\ }\ 998244353 $ で求めてください。 期待値を $ \text{mod\ }\ 998244353 $ で求めるとは 求める期待値は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な $ 2 $ つの整数 $ P $, $ Q $ を用いて $ \frac{P}{Q} $ と表したとき、$ R\ \times\ Q\ \equiv\ P\pmod{998244353} $ かつ $ 0\ \leq\ R\ \lt\ 998244353 $ を満たす整数 $ R $ がただ一つ存在することが証明できます。 この $ R $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ R_1 $ $ R_2 $ $ \dots $ $ R_M $ $ B_1 $ $ B_2 $ $ \dots $ $ B_M $

$ s $ の期待値を $ \text{mod\ }\ 998244353 $ で出力せよ。

### 制約 - $ 1\leq\ N\ \leq\ 17 $ - $ 1\ \leq\ M\ \leq\ 10^5 $ - $ 1\ \leq\ R_i,\ B_i\ \leq\ N $ - 入力は全て整数 ### Sample Explanation 1 $ i $ 個目の赤い端子と $ j $ 個目の青い端子をケーブルで繋ぐことを $ (i,\ j) $ と表記します。 - $ (1,1),\ (2,2) $ の場合：$ \lbrace\ 1,3\ \rbrace $ と $ \lbrace\ 2\ \rbrace $ という $ 2 $ つの連結成分ができるので、$ s=2 $ です。 - $ (1,2),\ (2,1) $ の場合：全体が $ 1 $ つの連結成分になるので、$ s=1 $ です。 よって、$ s $ の期待値は $ \frac{3}{2}\ \equiv\ 499122178\ \pmod\ {998244353} $ です。 ### Sample Explanation 2 どのように繋いでも $ s=N $ になります。