#P18360. Journey through the Fractal

Journey through the Fractal

Journey through the Fractal

题目描述

一个 ii 级三角形是边长为 2i−12^{i-1} 的等边三角形。

按以下规则定义分形:

  • 一个 1 级分形就是一个 1 级三角形。
  • 对于 i≥1i\ge1,把三个 ii 级分形分别放在一个 ii 级三角形的三条边外侧,使它们像下图那样恰好接合,得到一个 i+1i+1 级分形。

1级、2级、3级分形的定义图

现在给定一个 LL 级分形。

Alice 可以选择组成该分形的任意一个三角形区域作为起点。随后,她每次可以移动到一个尚未访问过、且与当前三角形共边的三角形。仅在一个顶点接触不能移动。

Alice 最多可以移动 KK 次。她的得分是所有访问过的三角形的级别之和,起点的级别也计入得分。

求能够得到的最大得分对 998244353998244353 取模后的结果。注意,应先最大化实际得分,再取模;并不是最大化余数。

输入格式

一行两个整数 LL、KK。

输出格式

输出最大得分对 998244353998244353 取模后的结果。

数据范围

  • 输入中的数值均为整数。
  • 1≤L≤1091\le L\le10^9。
  • 1≤K≤10181\le K\le10^{18}。
  • 每个输入文件只有一组数据。

样例输入 1

3 4

样例输出 1

6

样例输入 2

998244353 100000000000000007

样例输出 2

756221200

样例解释

样例 1 中,可以按下图标号顺序依次访问四个 1 级三角形和一个 2 级三角形,移动四次,总得分为 1+1+1+2+1=61+1+1+2+1=6。

样例1中的访问路线