← 返回题目列表

AtCoder · abc220_e

H. 大型完美二叉树上的距离

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

分数: 500 点

问题陈述

我们有一棵树 2^N-1 顶点。
顶点已编号 1 通过 2^N-1。对于每个 1\leq i < 2^{N-1},存在以下边:

  • 连接顶点的无向边 i 和顶点 2i,
  • 连接顶点的无向边 i 和顶点 2i+1.

没有其他边缘。

设两个顶点之间的距离为连接这两个顶点的简单路径中的边数。

求模数 998244353,顶点对 (i, j) 使得它们之间的距离是 D.

约束

  • 2 \leq N \leq 10^6
  • 1 \leq D \leq 2\times 10^6
  • 输入中的所有值都是整数。

输入

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

N D

输出

打印答案。


样本输入 1

3 2

示例输出 1

14

下图描述了给定的树。

Figure

有 14 顶点对,它们之间的距离为 2: (1,4),(1,5),(1,6),(1,7),(2,3),(3,2),(4,1),(4,5),(5,1),(5,4),(6,1),(6,7),(7,1),(7,6).


示例输入 2

14142 17320

示例输出 2

11284501