Distinct Fillings on a 1×(n-1) Grid

We have a 1×(n-1) grid where each cell is numbered from 1 to n-1. In each cell, you may choose one of two options:

• Leave the cell empty.
• Fill the cell with a positive integer that is at most equal to its cell number.

A filling scheme is called valid if no two filled cells have the same number. Cirno is interested in finding the number of valid schemes in which exactly k cells are filled. Since the answer can be large, output it modulo \(998244353\).

Note: Every filled cell at position \(i\) (1-indexed among cells 1 to n-1) has \(i\) choices initially; however, when filling multiple cells, the numbers chosen must be distinct. A dynamic programming formulation can be used where for each cell, if we choose to fill it, the number of available choices is the number of integers from 1 to i that have not been previously used.

The following recurrence can be applied if we define \(dp[i][j]\) as the number of ways to process the first \(i\) cells to get exactly \(j\) filled cells. When considering the \((i+1)\)th cell, if we decide to fill it, there are \((i+1) - j\) available choices (since \(j\) numbers have already been used). Otherwise, we leave it empty.

The answer is \(dp[n-1][k]\) modulo \(998244353\).

inputFormat

The input consists of a single line containing two integers n and k (\(2 \le n \le \text{upper bound}\), \(0 \le k \le n-1\)). Here, n denotes the grid has n-1 cells and k is the exact number of cells to be filled.

For example:

5 2

outputFormat

Output a single integer, the number of valid filling schemes with exactly k filled cells modulo \(998244353\).

For example, for the input above the output should be:

25

sample

2 1

1