← 返回题目列表

AtCoder · utpc2024_j

J. 分形之旅

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

配点 : 100 点

問題文

1 边长为 2^{i-1} 的正三角形,等级 如果你尝试训练 i 的三角形称作。此外,按照以下规则生成的图形称作等级 如果你尝试训练 i 的分形称为。

  • 等级 如果你尝试训练 1 的分形是由等级 1 的三角形构成的
  • 等级 如果你尝试训练 i + 1 (i \geq 1) 的分形是由等级 i 三角形 3 使水平仪正好接触到每一条边 i 是一个布置了分形的图形(详细请参阅图示)

在这里,层级 L 有一个分形。

Alice 首先从构成分形的三角形中选择自己喜欢的一个三角形作为起点。 1 然后,如果有尚未访问且与当前位置的三角形通过边相邻的三角形,她可以选择一个进行移动。 1 Alice 选择其中一个并移动。

Alice 最多可以移动 K 次。她访问过的三角形(包括起点三角形)的等级总和,分数。

作为分数的可能最大值为 998244353 除后的余数。请注意,这里不是求用998244353 除后的余数的最大值。如图

制約

  • 所有输入均为整数
  • 1 \leq L \leq 10^9
  • 1 \leq K \leq 10^{18}

入力

输入是按以下格式从标准输入给出的。

L K

出力

最高分 998244353 取余的结果。 由于是


入力例 1

3 4

出力例 1

6

所示,通过移动,可以得到等级 1 的三角形 4 个,等级 2 的三角形 1 可以访问。

另外,图中三角形内写的数字表示访问该三角形的顺序。


入力例 2

998244353 100000000000000007

出力例 2

756221200

最高分 998244353 后的余数。