题目描述

给定正整数 $N$ 和 $K$。请计算满足以下所有条件的整数序列 $\bigl(f(0),\ f(1),\ \ldots,\ f(2^N-1)\bigr)$ 的个数，并将答案对 $998244353$ 取模后输出。

• 对于任意非负整数 $x$（$0\leq x \leq 2^N-1$），都有 $0\leq f(x)\leq K$。
• 对于任意非负整数 $x,\ y$（$0\leq x, y \leq 2^N-1$），都有 $f(x) + f(y) = f(x\ \mathrm{AND}\ y) + f(x\ \mathrm{OR}\ y)$。

其中，$\mathrm{AND}$ 和 $\mathrm{OR}$ 分别表示按位与和按位或运算。

输入格式

输入为一行，包含两个整数 $N$ 和 $K$。

输出格式

输出满足条件的整数序列的个数，对 $998244353$ 取模后的结果。

样例 1

输入

2 1

输出

6

样例 2

输入

2 2

输出

19

样例 3

输入

100 123456789123456789

输出

34663745

说明/提示

数据范围

• $1\leq N\leq 3\times 10^5$
• $1\leq K\leq 10^{18}$

样例解释 1

满足条件的整数序列共有 $6$ 个：

• $(0,0,0,0)$
• $(0,1,0,1)$
• $(0,0,1,1)$
• $(1,0,1,0)$
• $(1,1,0,0)$
• $(1,1,1,1)$

由 ChatGPT 4.1 翻译