Background

${\rm CYJian}$ recently thought of Water Triangle and felt it was too easy, so he came up with a more interesting version.

Problem Description

Given $N$ and $K$, compute:

$$\sum_{i=1}^{K} f[N][i] \ (\bmod\ 998244353)$$

where:

$$f[i][j] = f[i-1][j] + f[i][j-1] + f[i-1][j-1] \ (i>1, j \leq i)$$$$f[1][1] = 1 \qquad f[i][0] = 0 \qquad f[i][j] = 0 \ (j>i)$$

Input Format

The first line contains two positive integers $N$ and $K$.

Output Format

Output one line containing the value of the expression above.

1 1

1

2 2

3

3 3

11

4 3

23

Hint

Constraints:

For $10\%$ of the testdata: $1 \leq N \leq 10^3 \qquad 1 \leq K \leq 10^2$.

For $30\%$ of the testdata: $1 \leq N \leq 10^6 \qquad 1 \leq K \leq 10^2$.

For $50\%$ of the testdata: $1 \leq N \leq 10^{18} \qquad 1 \leq K \leq 10^2$.

For another $20\%$ of the testdata: $1 \leq N \leq 10^6 \qquad 1 \leq K \leq 10^3$.

For $100\%$ of the testdata: $1 \leq N \leq 10^{18} \qquad 1 \leq K \leq 10^3$.

It is guaranteed that $K \leq N$.

Update: The time limit has been changed as follows: for test points $1$~$35$, the time limit is $600 \text{ ms}$; for test points $36$~$50$, the time limit is $400 \text{ ms}$.

Translated by ChatGPT 5