Description

“Then… how long are you going to stand there? Sit down before the tea gets cold.”

“Damn it… Fine, fine!” Subaru walked forward and sat opposite the witch. Besides two cups of tea, there was also a black-and-white chessboard on the table.

“This is…?” Subaru pointed at the board and asked.

“This is Witch Chess. I invited you here to answer a question that I have been thinking about for years but still can’t solve. If you solve it, I will give you and Emilia the right to take the trial… Otherwise…” An unsettling smile appeared on the witch’s face. “You might end up looping endlessly in the Sanctuary…?”

Subaru broke out in a cold sweat and asked tremblingly, “So what is the question?”

The witch picked up a piece beside her and said slowly: “As you can see, this is an $n\times n$ chessboard made of $n^2$ cells, and each cell can contain at most one piece. Unlike a normal board, this board is cyclic. That is, the cell to the right of row $i$, column $n$ is row $i$, column $1$; the cell below row $n$, column $i$ is row $1$, column $i$; and so on. The piece in my hand is called a ‘Sin Archbishop’. In one move, it can move any number of cells in any diagonal direction. The cells a piece can reach in one move are called the cells it controls. If one piece controls the cell where another piece is located, then the board configuration is unstable; otherwise, it is stable. Now, can you place exactly $m$ ‘Sin Archbishops’ on the board such that the whole configuration is stable?”

High-resolution version of the figure above

Subaru thought for a while, then operated on the board and quickly completed the witch’s task, saying: “Then quickly give me the right to take the trial!”

The witch said: “No… I still have one more question not solved…”

Subaru: “Hey, you’re cheating!”

The witch ignored Subaru and continued: “Now the question is: how many essentially different stable configurations are there such that there are exactly $m$ ‘Sin Archbishops’ in the configuration? Two configurations are essentially different if and only if there exists a cell that has a piece in one configuration but not in the other.”

Subaru got even angrier, because he could not solve it. So he asked you for help. You only need to output the answer modulo $998244353$.

Input Format

One line contains two positive integers $n,m$, representing the board size and the number of pieces you need to place.

Output Format

One line contains one positive integer, representing the answer modulo $998244353$.

1 1

1

2 2

4

3 2

18

10 5

8647680

Hint

Sample 1: Placing one piece on a $1\times1$ board obviously has only one configuration.

Sample 2: There are the following four stable configurations (use . for an empty cell, and o for a ‘Sin Archbishop’):

oo .o .. o.
.. .o oo o.

Sample 3: All $18$ stable configurations can be viewed here.

Constraints

For all data, $1\le n<998244353$, $0\le m\le\min\{n,10^7\}$.

Subtask 1 (5 pts): Guaranteed $m=0$.

Subtask 2 (10 pts): Guaranteed $m=1$.

Subtask 3 (10 pts): Guaranteed $1\le n\le 4$.

Subtask 4 (20 pts): Guaranteed that $n$ is odd.

Subtask 5 (25 pts): Guaranteed $n\le 10^7$.

Subtask 6 (30 pts): No additional constraints.

Translated by ChatGPT 5