题目描述

正整数 $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$ で割った余りを出力してください．

题目大意

给定两个正整数 $n,k$，找到对于满足下列条件的长度为 $2^n$ 下标从 $0$ 开始的序列的个数：

1. $0\le a_i\le k$
2. $a_i+a_j=a_{i\operatorname{and} j}+a_{i\operatorname{or}j},0\le i,j< 2^n$

• $1\le n\le 3\times 10^5,1\le k\le 10^{18}$

2 1

6

2 2

19

100 123456789123456789

34663745

提示

制約

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

Sample Explanation 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)$