配点 : 100 点
問題文
0 以上 2^M 的整数组成 N 序列 A 考虑以下所有值,并计算它们的总和。 除以 998244353 求余数。
- (A_1\times A_2) \oplus (A_2\times A_3) \oplus \ldots \oplus (A_{N-1}\times A_N) 输出为 2^M 时的余数
但是 \oplus 以位为单位 \mathrm{XOR} 代表一个操作。
位单位 \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)。
制約
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- 所有输入均为整数 仅当
入力
输入将以以下形式从标准输入给出。
N M
出力
打印答案。
入力例 1
2 1
出力例 1
1
A=(1,1) 仅当 A_1\times A_2 = 1 ,否则 0 ,所以答案是 1 。
入力例 2
2 2
出力例 2
16
入力例 3
314 159
出力例 3
856758166