201443: [AtCoder]ARC144 D - AND OR Equation

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

给定两个正整数 $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}$

加入题单

上一题 下一题 算法标签: