AT_KeioPC2025_m Popcount MST

長さ $ N $ の整数列 $ A = (A_0, \dots , A_{N-1}) $ に対し、 $ f(A) $ を以下のように定義します。ここで $ a \ \mathrm{AND} \ b $ は $ a $ と $ b $ のビットごとの論理積を表します。 - 頂点に $ 0 $ から $ 2^N-1 $ の番号がついた $ 2^N $ 頂点の重み付き完全グラフ $ G $ を考える。ただし、頂点 $ i $ と頂点 $ j $ を結ぶ辺の重みは $ \displaystyle A_{\mathrm{popcount}(i \ \mathrm{AND} \ j)} $ である。このときのグラフ $ G $ の最小全域木にふくまれる辺の重みの総和を $ f(A) $ と定める。 長さ $ N $ の整数列 $ B = (B_0, \dots , B_{N-1}) $ が与えられます。 $ B $ の各要素は $ -1 $ または $ 1 $ 以上 $ M $ 以下です。 $ B $ の要素のうち、 $ -1 $ をすべて $ 1 $ 以上 $ M $ 以下の整数に置き換えて得られる数列 $ B' $ は、 $ B $ に含まれる $ -1 $ の個数を $ q $ とすると $ M^q $ 通りあります。 考えられる $ B' $ すべてに対する $ f(B') $ の総和を $ 998244353 $ で割ったあまりを求めてください。 $ \mathrm{popcount} $ とは？非負整数 $ x $ について $ \operatorname{popcount}(x) $ とは、 $ x $ を $ 2 $ 進法で表記したときの $ 1 $ の個数です。 より厳密には、非負整数 $ x $ について $ \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) $ が成り立っているとき $ \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i $ です。 例えば、 $ 13 $ を $ 2 $ 進法で表記すると `1101` なので、 $ \operatorname{popcount}(13)=3 $ となります。

入力は以下の形式で標準入力から与えられる。 > $ N \ M $ $ B_0 \ \dots \ B_{N-1} $

答えを出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ 1 \le B_i \le M $ を満たすデータセットに正解した場合 $ 1 $ 点が与えられる。 ### Sample Explanation 1 考えられる $ B' $ は以下の $ 2 $ 通りです。 - $ B' = (1, 2) $ のとき、辺 $ (0, 1), (0, 2), (0, 3) $ からなる全域木が最小全域木の一例で、辺の重みの総和は $ 3 $ となります。 - $ B' = (2, 2) $ のとき、辺 $ (0, 1), (1, 2), (2, 3) $ からなる全域木が最小全域木の一例で、辺の重みの総和は $ 6 $ となります。 よって、すべての $ B' $ に対する $ f(B') $ の総和は $ 9 $ となります。 ### Constraints - $ 1 \le N, M \le 125000 $ - $ B_i $ は $ -1 $ または $ 1 $ 以上 $ M $ 以下の整数