← 返回题目列表

AtCoder · pakencamp_2022_day3_l

L. X 和异或

中文机器翻译题面 查看原题

配点 : 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