题目描述

整数 $N$ が与えられます。整数列 $A\ =\ (1,\ 2,\ \ldots,\ N)$ に対して、次の操作をちょうど $K$ 回行います：

• 操作を行う時点での $A$ の項数を $n$ とする。$1\leq\ i\ \leq\ n$ かつ $i\equiv\ 1\pmod{3}$ となるすべての $i$ に対して、$A$ の $i$ 番目の項を削除する。この操作はすべての $i$ について同時に行う。

$K$ 回の操作後の $A$ の項の総和を $998244353$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $K$

输出格式

$K$ 回の操作後の $A$ の項の総和を $998244353$ で割った余りを出力してください。

题目大意

给定含有 $n$ 个元素的序列 $\{A\}$，初始时 $A_i=i$。

现在对这个序列进行 $k$ 次操作：每次操作是在上一次操作后剩余的序列中删去所处位置 $i$ 满足 $i\equiv1(\bmod3)$ 的数字。

询问进行 $k$ 次操作后的序列所有数字的和。

10 2

25

10 10

0

10000 10

862816

提示

制約

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

Sample Explanation 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$ です。

Sample Explanation 2

- $2$ 回目の操作を行うと、$A\ =\ (3,\ 5,\ 8,\ 9)$ となります（入力例 1 と同様です）。 - $3$ 回目の操作を行うと、$A\ =\ (5,\ 8)$ となります。 - $4$ 回目の操作を行うと、$A\ =\ (8)$ となります。 - $5$ 回目の操作を行うと、$A$ は空になります。 - $6$ 回目以降の操作では、$A$ は空のままで、その項の総和は $0$ です。