AT_arc227_e [ARC227E] Shift and XOR Switches

$ 0 $ と $ 1 $ からなる長さ $ N $ の数列 $ B=(B_1,B_2,\ldots,B_N) $ があります。 はじめ、 $ B_1=1 $ であり、それ以外の要素は $ 0 $ です。 $ M $ 個のスイッチがあり、スイッチ $ i $ ( $ 1 \le i \le M $ ) には整数 $ A_i $ が書かれています。 スイッチ $ i $ を押すと、操作を行う直前の状態を用いて、 $ 1 \le j \le N $ を満たすすべての整数 $ j $ について $ B_j $ を同時に次のように変更します。 \\\[ B\_j \\leftarrow \\begin{cases} B\_j \\oplus B\_{j-A\_i} & (A\_i \\lt j),\\\\ B\_j & (j \\le A\_i) \\end{cases} \\\] 各スイッチは $ 0 $ 回または $ 1 $ 回押すことができ、スイッチを押す順番は自由です。 最終的な列 $ B $ としてあり得るものの個数を $ 998244353 $ で割った余りを求めてください。 ビット単位 $ \mathrm{XOR} $ 演算とは非負整数 $ A, B $ のビット単位 $ \mathrm{XOR} $ 、 $ A \oplus B $ は、 以下のように定義されます。 - $ A \oplus B $ を二進表記した際の $ 2^k $ ( $ k \geq 0 $ ) の位の数は、 $ A, B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $ 、 そうでなければ $ 0 $ である。 例えば、 $ 3 \oplus 5 = 6 $ となります (二進表記すると: $ 011 \oplus 101 = 110 $ )。 一般に $ k $ 個の非負整数 $ p_1, p_2, p_3, \dots, p_k $ のビット単位 $ \mathrm{XOR} $ は $ (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) $ と定義され、 これは $ p_1, p_2, p_3, \dots, p_k $ の順番によらないことが証明できます。

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

最終的な列 $ B $ としてあり得るものの個数を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 最終的な列としてあり得るものは、次の $ 4 $ 個です。 - $ (1,0,0,0) $ - $ (1,0,1,0) $ - $ (1,0,0,1) $ - $ (1,0,1,1) $ ### Sample Explanation 2 最終的な列としてあり得るものは、 $ (1,0) $ と $ (1,1) $ の $ 2 $ 個です。 ### Constraints - $ 2 \le N \le 2 \times 10^5 $ - $ 1 \le M \le 2 \times 10^5 $ - $ 1 \le A_i \lt N $ ( $ 1 \le i \le M $ ) - 入力される数値はすべて整数