Problem Description

${\rm CYJian}$ recently recalled the problem "Water's Triangle" and found it too easy, so he came up with a more interesting version.

Problem Description

Given \( N \) and \( K \), please calculate:

\[ \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] \quad (i > 1, j \leq i) \]

\[ f[1][1] = 1 \quad f[i][0] = 0 \quad f[i][j] = 0 \ (j > i) \]

Input Format

The first line contains two positive integers \( N \) and \( K \).

Output Format

Output a single line containing the value of the above expression.

Sample Input and Output

Sample Input #1

1 1

Sample Output #1

1

Sample Input #2

2 2

Sample Output #2

3

Sample Input #3

3 3

Sample Output #3

11

Sample Input #4

4 3

Sample Output #4

23

Notes/Hints

For \( 10\% \) of the data: \( 1 \leq N \leq 10^3 \quad 1 \leq K \leq 10^2 \)

For \( 30\% \) of the data: \( 1 \leq N \leq 10^6 \quad 1 \leq K \leq 10^2 \)

For \( 50\% \) of the data: \( 1 \leq N \leq 10^{18} \quad 1 \leq K \leq 10^2 \)

For an additional \( 20\% \) of the data: \( 1 \leq N \leq 10^6 \quad 1 \leq K \leq 10^3 \)

For \( 100\% \) of the data: \( 1 \leq N \leq 10^{18} \quad 1 \leq K \leq 10^3 \)

It is guaranteed that \( K \leq N \).

Update: The time limit has been changed: Test points \( 1 \) to \( 35 \) have a time limit of \( 600ms \), and test points \( 36 \) to \( 50 \) have a time limit of \( 400ms \).

见题面 Input 部分

见题面 Output 部分