AT_arc224_f [ARC224F] AND/OR

You are given a length- $ N $ sequence of non-negative integers $ A=(A_1,A_2,\dots,A_N) $ and an integer $ K $ . Initially, $ x=0 $ . For $ i=1,2,\dots,N $ in this order, let us choose one of the following two operations to perform. - Operation $ 1 $ : Replace $ x $ with $ x $ $ {\rm AND} $ $ A_i $ . - Operation $ 2 $ : Replace $ x $ with $ x $ $ {\rm OR} $ $ A_i $ . Here, operation $ 2 $ must be chosen at most $ K $ times in total. $ {\rm AND} $ denotes the bitwise $ {\rm AND} $ operation, and $ {\rm OR} $ denotes the bitwise $ {\rm OR} $ operation. Let $ M $ be the maximum possible value of $ x $ after all operations are finished. Find the number, modulo $ 998244353 $ , of operation sequences such that the final $ x $ equals $ M $ . Here, two operation sequences are distinguished if and only if there exists an integer $ j $ ( $ 1 \le j \le N $ ) such that the operation chosen at the $ j $ -th step differs between them. $ T $ test cases are given; solve each of them. What is the bitwise $ \mathrm{AND} $ operation? The bitwise $ \mathrm{AND} $ of non-negative integers $ A, B $ , denoted $ A\ \mathrm{AND}\ B $ , is defined as follows. - The digit in the $ 2^k $ ( $ k \geq 0 $ ) place of the binary representation of $ A\ \mathrm{AND}\ B $ is $ 1 $ if the corresponding digits of $ A $ and $ B $ in binary are both $ 1 $ , and $ 0 $ otherwise. For example, $ 3\ \mathrm{AND}\ 5 = 1 $ (in binary: $ 011\ \mathrm{AND}\ 101 = 001 $ ). What is the bitwise $ \mathrm{OR} $ operation? The bitwise $ \mathrm{OR} $ of non-negative integers $ A, B $ , denoted $ A\ \mathrm{OR}\ B $ , is defined as follows. - The digit in the $ 2^k $ ( $ k \geq 0 $ ) place of the binary representation of $ A\ \mathrm{OR}\ B $ is $ 1 $ if at least one of the corresponding digits of $ A $ and $ B $ in binary is $ 1 $ , and $ 0 $ otherwise. For example, $ 3\ \mathrm{OR}\ 5 = 7 $ (in binary: $ 011\ \mathrm{OR}\ 101 = 111 $ ).

The input is given from Standard Input in the following format, where $ \mathrm{case}_i $ denotes the $ i $ -th test case: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

Output $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 This input contains five test cases. For the first test case, $ M=7 $ , and the following three operation sequences achieve the final value $ x=M $ . - Perform the operations in the order $ 1,1,2,2,2 $ . $ x $ changes as $ 0 \to 0 \to 0 \to 1 \to 3 \to 7 $ . - Perform the operations in the order $ 1,2,1,2,2 $ . $ x $ changes as $ 0 \to 0 \to 7 \to 1 \to 3 \to 7 $ . - Perform the operations in the order $ 2,1,1,2,2 $ . $ x $ changes as $ 0 \to 3 \to 3 \to 1 \to 3 \to 7 $ . For the fifth test case, note that the answer should be output modulo $ 998244353 $ . ### Constraints - $ 1 \le T \le 10^4 $ - $ 1 \le K \le N \le 2 \times 10^5 $ - $ 0 \le A_i < 2^{60} $ - The sum of $ N $ in each input is at most $ 2 \times 10^5 $ . - All input values are integers.