← 返回题目列表

AtCoder · arc144_d

D. AND OR 方程

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你正整数 N 和 K。求模数 998244353,整数序列 \bigl(f(0), f(1), \ldots, f(2^N-1)\bigr) 满足以下所有条件:

  • 0\leq f(x)\leq K 对于所有非负整数 x (0\leq x \leq 2^N-1).
  • f(x) + f(y) = f(x \,\mathrm{AND}\, y) + f(x \,\mathrm{OR}\, y) 对于所有非负整数 x 和 y (0\leq x, y \leq 2^N-1)

在这里, \mathrm{AND} 和 \mathrm{OR} 分别表示按位AND和OR。

约束

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

输入

输入由标准输入按以下格式给出:

N K

输出

打印数字,模数 998244353,满足条件的整数序列。


示例输入 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