Problem Statement

You are given an integer $N. On an integer sequence A = (1, 2, \ldots, N)$, let us do the operation below exactly K times.

• Let n be the current number of terms in A. For all i such that $1\leq i \leq n$ and $i\equiv 1\pmod{3},$ delete the i-th term of A, simultaneously.

Find the sum of the terms of A after K operations, modulo 998244353.

Input

Input is given from Standard Input from the following format:
N K

Output

Print the sum of the terms of A after K operations, modulo 998244353.

Constraints

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

Sample Input 1

10 2

Sample Output 1

25

• Initially, we have A = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10).
• After the first operation, we have A = (2, 3, 5, 6, 8, 9).
• After the second operation, we have A = (3, 5, 8, 9).
• The sum of the terms here is 3 + 5 + 8 + 9 = 25.

Sample Input 2

10 10

Sample Output 2

0

• After the second operation, we have A = (3, 5, 8, 9) (same as Sample Input 1).
• After the third operation, we have A = (5, 8).
• After the fourth operation, we have A = (8).
• After the fifth operation, A is empty.
• In the sixth and subsequent operations, A remains empty, where the sum of the terms is 0.

Sample Input 3

10000 10

Sample Output 3

862816

见题面 Input 部分

见题面 Output 部分