Contest Duration: - (local time) (120 minutes) Back to Home
D - AND OR Equation /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

• 任意の非負整数 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


入力例 1

2 1


出力例 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)

入力例 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