/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
正整数 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} はそれぞれビットごとの論理積，論理和を表します．
制約
- 1\leq N\leq 3\times 10^5
- 1\leq K\leq 10^{18}
入力
入力は以下の形式で標準入力から与えられます．
N K
出力
条件を満たす整数列の個数を 998244353 で割った余りを出力してください．
入力例 1
2 1
出力例 1
6
条件を満たす整数列は以下の 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)
入力例 2
2 2
出力例 2
19
入力例 3
100 123456789123456789
出力例 3
34663745
Score : 700 points
Problem Statement
You are given positive integers N and K. Find the number, modulo 998244353, of integer sequences \bigl(f(0), f(1), \ldots, f(2^N-1)\bigr) that satisfy all of the following conditions:
- 0\leq f(x)\leq K for all non-negative integers x (0\leq x \leq 2^N-1).
- f(x) + f(y) = f(x \,\mathrm{AND}\, y) + f(x \,\mathrm{OR}\, y) for all non-negative integers x and y (0\leq x, y \leq 2^N-1)
Here, \mathrm{AND} and \mathrm{OR} denote the bitwise AND and OR, respectively.
Constraints
- 1\leq N\leq 3\times 10^5
- 1\leq K\leq 10^{18}
Input
Input is given from Standard Input in the following format:
N K
Output
Print the number, modulo 998244353, of integer sequences that satisfy the conditions.
Sample Input 1
2 1
Sample Output 1
6
The following six integer sequences satisfy the conditions:
- (0,0,0,0)
- (0,1,0,1)
- (0,0,1,1)
- (1,0,1,0)
- (1,1,0,0)
- (1,1,1,1)
Sample Input 2
2 2
Sample Output 2
19
Sample Input 3
100 123456789123456789
Sample Output 3
34663745