AT_arc227_e [ARC227E] Shift and XOR Switches

There is a length- $ N $ sequence $ B=(B_1,B_2,\ldots,B_N) $ consisting of $ 0 $ and $ 1 $ . Initially, $ B_1=1 $ , and all other elements are $ 0 $ . There are $ M $ switches, and the integer $ A_i $ is written on switch $ i $ ( $ 1 \le i \le M $ ). When switch $ i $ is pressed, using the state immediately before the operation, $ B_j $ is simultaneously changed as follows for every integer $ j $ satisfying $ 1 \le j \le N $ : $$ B_j \leftarrow \begin{cases} B_j \oplus B_{j-A_i} & (A_i \lt j),\\ B_j & (j \le A_i) \end{cases} $$ Each switch can be pressed zero times or once, and the switches may be pressed in any order. Find the number, modulo $ 998244353 $ , of possible final sequences $ B $ . ::::info[What is the bitwise $ \mathrm{XOR} $ operation?] The bitwise $ \mathrm{XOR} $ of non-negative integers $ A $ and $ B $ , denoted $ A \oplus B $ , is defined as follows: - The digit in the $ 2^k $ 's place ( $ k \geq 0 $ ) of $ A \oplus B $ , written in binary, is $ 1 $ if exactly one of the digits in the $ 2^k $ 's place of $ A $ and $ B $ , written in binary, is $ 1 $ , and $ 0 $ otherwise. For example, $ 3 \oplus 5 = 6 $ (in binary: $ 011 \oplus 101 = 110 $ ). In general, the bitwise $ \mathrm{XOR} $ of $ k $ non-negative integers $ p_1, p_2, p_3, \dots, p_k $ is defined as $ (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) $ , and it can be proved that this does not depend on the order of $ p_1, p_2, p_3, \dots, p_k $ . ::::

The input is given from Standard Input in the following format: > $ N $ $ M $ > $ A_1 $ $ A_2 $ $ \ldots $ $ A_M $

Output the number, modulo $ 998244353 $ , of possible final sequences $ B $ .

### Sample Explanation 1 There are four possible final sequences: - $ (1,0,0,0) $ - $ (1,0,1,0) $ - $ (1,0,0,1) $ - $ (1,0,1,1) $ ### Sample Explanation 2 There are two possible final sequences: $ (1,0) $ and $ (1,1) $ . ### 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 $ ) - All input values are integers.