D - AND OR Equation 解説 /

実行時間制限: 2 sec / メモリ制限: 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