题目描述

给定正整数 $N,\ M$。

请计算满足以下条件的长度为 $N$ 的正整数序列 $A=(A_1,\ A_2,\ \dots,\ A_N)$ 的个数，并将结果对 $998244353$ 取模后输出。

• $1\leq A_1< A_2< \dots< A_N\leq M$
• 设 $B_i = A_1\oplus A_2\oplus \dots\oplus A_i$，则 $B_1< B_2< \dots< B_N$

其中，$\oplus$ 表示按位异或（XOR）运算。

按位异或（XOR）运算的定义如下：对于非负整数 $A,\ B$，$A\oplus B$ 的二进制表示中，每一位 $2^k$（$k\geq 0$）上的数字，如果 $A$ 和 $B$ 的该位中恰有一个为 $1$，则结果为 $1$，否则为 $0$。

例如，$3\oplus 5=6$（二进制表示为：$011\oplus 101=110$）。 一般来说，$k$ 个非负整数 $p_1,\ p_2,\ p_3,\ \dots,\ p_k$ 的按位异或为 $(\dots((p\_1\oplus p\_2)\oplus p\_3)\oplus\dots\oplus p\_k)$，并且可以证明其结果与顺序无关。

输入格式

输入从标准输入读取，格式如下：

$N$ $M$

输出格式

请输出答案。

样例 1

输入

2 4

输出

5

样例 2

输入

4 4

输出

0

样例 3

输入

10 123456789

输出

205695670

说明/提示

限制条件

• $1\leq N\leq M<2^{60}$
• 输入的所有数均为整数

样例解释 1

例如，当 $(A_1, A_2) = (1, 3)$ 时，$A_1 < A_2$，且 $B_1 = A_1 = 1,\ B_2 = A_1\oplus A_2 = 2$，因此 $B_1 < B_2$，满足条件。除此之外，$(A_1, A_2) = (1, 2),\ (1, 4),\ (2, 4),\ (3, 4)$ 也满足条件。

由 ChatGPT 4.1 翻译