题目描述

给定一个整数 $N$。对于整数序列 $A = (1, 2, \ldots, N)$，你需要恰好进行 $K$ 次如下操作：

• 设当前 $A$ 的项数为 $n$。对于所有满足 $1 \leq i \leq n$ 且 $i \equiv 1 \pmod{3}$ 的 $i$，同时删除 $A$ 的第 $i$ 项。

请你求出经过 $K$ 次操作后，$A$ 的所有项的总和对 $998244353$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$

输出格式

输出经过 $K$ 次操作后，$A$ 的所有项的总和对 $998244353$ 取模的结果。

样例 1

输入

10 2

输出

25

样例 2

输入

10 10

输出

0

样例 3

输入

10000 10

输出

862816

说明/提示

限制条件

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

样例解释 1

• 初始时，$A = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)$。
• 第 $1$ 次操作后，$A = (2, 3, 5, 6, 8, 9)$。
• 第 $2$ 次操作后，$A = (3, 5, 8, 9)$。
• 此时 $A$ 的项的总和为 $3 + 5 + 8 + 9 = 25$。

样例解释 2

• 第 $2$ 次操作后，$A = (3, 5, 8, 9)$（与样例 1 相同）。
• 第 $3$ 次操作后，$A = (5, 8)$。
• 第 $4$ 次操作后，$A = (8)$。
• 第 $5$ 次操作后，$A$ 为空。
• 第 $6$ 次及之后的操作，$A$ 仍为空，其项的总和为 $0$。

由 ChatGPT 4.1 翻译