Description

In fact, a quadrilateral chain can be abstracted as a $1\times (n - 1)$ grid. Each cell is numbered $1$, $2$, $\ldots$, $n-1$, respectively.

Each cell can take one of two choices:

• Leave it empty.
• Fill in a positive integer that is less than or equal to its own index.

If a filling scheme does not have two cells filled with the same number, Cirno calls it a valid scheme.

Cirno wants to know the number of valid schemes in which exactly $k$ cells are filled with numbers, modulo $998244353$.

Input Format

One line containing two integers $n$, $k$.

Output Format

One line containing one integer, the answer.

10 5

42525

642 357

409821948

666666 233333

791003566

Hint

Constraints

This problem uses bundled testdata.

• Subtask 1 ( $20\%$ ): $n,k \le 10$.
• Subtask 2 ( $20\%$ ): $n,k \le 1000$.
• Subtask 3 ( $60\%$ ): no special constraints.

For $100\%$ of the testdata: $0 \le k < n \le 10^6$.

Notes

• The following references are not necessary to read.

Reference

• [1] CNKI - Some Extremal Problems of Quadrilateral Chains - Xiamen University - Zeng Yanqiu
  http://kns.cnki.net/KCMS/detail/detail.aspx?dbcode=CMFD&filename=2007056552.nh
• [2] CNKI - On the Hamming Gracefulness of Quadrilateral Cactus Graphs - Education Technology Center, Jilin Engineering and Technical Teachers College; College of Science and Engineering, Hainan University - Li Xiufen; Pan Wei
  http://www.cnki.com.cn/Article/CJFDTotal-CCYD200806009.htm

Translated by ChatGPT 5