← 返回题目列表

AtCoder · arc135_f

F. 删除 1、4、7、...

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

分数: 1000 点

问题陈述

给你一个整数 N。在整数序列上 A = (1, 2, \ldots, N),让我们准确执行下面的操作 K 次。

  • 让 n 是当前的项数 A。对于所有人 i 这样 1\leq i \leq n 和 i\equiv 1\pmod{3},删除 i第 学期 A,同时。

求以下项的总和 A 之后 K 运算,模数 998244353.

约束

  • 1\leq N\leq 10^{14}
  • 1\leq K\leq 100

输入

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

N K

输出

打印各项的总和 A 之后 K 运算,模数 998244353.


示例输入 1

10 2

示例输出 1

25
  • 最初,我们有 A = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10).
  • 第一次操作后,我们有 A = (2, 3, 5, 6, 8, 9).
  • 第二次操作后,我们有 A = (3, 5, 8, 9).
  • 这里各项的总和是 3 + 5 + 8 + 9 = 25.

示例输入 2

10 10

示例输出 2

0
  • 第二次操作后,我们有 A = (3, 5, 8, 9) (与示例输入 1 相同)。
  • 第三次操作后,我们有 A = (5, 8).
  • 第四次操作后,我们有 A = (8).
  • 第五次操作后, A 为空。
  • 在第六次及后续操作中, A 仍为空,其中各项之和为 0.

示例输入 3

10000 10

示例输出 3

862816