#P13666. [ARC144D] AND OR Equation

    ID: 12868 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-双射计数插板法乘法原理加法原理阶乘逆元预处理快速幂

[ARC144D] AND OR Equation

题目描述

给定正整数 NN 和 KK。请计算满足以下所有条件的整数序列 (f(0), f(1), …, f(2N−1))\bigl(f(0),\ f(1),\ \ldots,\ f(2^N-1)\bigr) 的个数,并将答案对 998244353998244353 取模后输出。

  • 对于任意非负整数 xx(0≤x≤2N−10\leq x \leq 2^N-1),都有 0≤f(x)≤K0\leq f(x)\leq K。
  • 对于任意非负整数 x, yx,\ y(0≤x,y≤2N−10\leq x, y \leq 2^N-1),都有 $f(x) + f(y) = f(x\ \mathrm{AND}\ y) + f(x\ \mathrm{OR}\ y)$。

其中,AND\mathrm{AND} 和 OR\mathrm{OR} 分别表示按位与和按位或运算。

输入格式

输入为一行,包含两个整数 NN 和 KK。

输出格式

输出满足条件的整数序列的个数,对 998244353998244353 取模后的结果。

输入输出样例 #1

输入 #1

2 1

输出 #1

6

输入输出样例 #2

输入 #2

2 2

输出 #2

19

输入输出样例 #3

输入 #3

100 123456789123456789

输出 #3

34663745

说明/提示

数据范围

  • 1≤N≤3×1051\leq N\leq 3\times 10^5
  • 1≤K≤10181\leq K\leq 10^{18}

样例解释 1

满足条件的整数序列共有 66 个:

  • (0,0,0,0)(0,0,0,0)
  • (0,1,0,1)(0,1,0,1)
  • (0,0,1,1)(0,0,1,1)
  • (1,0,1,0)(1,0,1,0)
  • (1,1,0,0)(1,1,0,0)
  • (1,1,1,1)(1,1,1,1)