P6162 [Cnoi2020] Quadrilateral Chain

> A quadrilateral chain graph is a common quadrilateral network. It belongs to cactus graphs. It usually does not appear in the cross-section at the tail of a heavily doped single crystal. What appears is a closed non-quadrilateral ring network whose outer boundary is a set of impurity-enriched stripes. However, because of its complex characteristics, it often appears in scenarios describing community connections, such as some well-known indescribable ones... As a smart and lively girl, Cirno got tired of the textbook-style long and boring concepts, and directly gave the diagram of a quadrilateral chain graph. 

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$.

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

One line containing one integer, the answer.

### 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