25669번 - Matrix Counting 다국어

We call an $n \times n$ matrix containing only 0s and 1s bad if and only if it contains exactly one 1 in each row and column.

Define $B$ to be a subrectangle of an $n \times n$ matrix $A$ if and only if there exist $1 \le l_1 \le r_1 \le n$ and $1 \le l_2 \le r_2 \le n$ such that

• $B$ is a $(r_1-l_1+1) \times (r_2-l_2+1)$ matrix.
• $B_{i,j} = A_{l_1+i-1, r_1+j-1}$ ($1 \le i \le r_1-l_1+1, 1 \le j \le r_2-l_2+1$)

Given two integers $n$ and $m$, you want to calculate how many $n \times n$ matrices $M$ containing only 0s and 1s are there such that:

1. $M$ is bad,
2. all its subrectangles of size $k \times k$ ($k = m + 1, m + 2, \ldots, n - 1$) are not bad.

Since the answer can be large, output it modulo $998\,244\,353$.

The first line contains two integers $n$ and $m$ ($1 \le m < n \le 10^5$).

Output a single line containing a single integer, indicating the answer modulo $998\,244\,353$.

In the first example, there are $6$ bad matrices. The second condition does not matter since $m + 1 = 3 > n - 1 = 2$. So the answer is $6$.

In the second example, there are $4$ matrices satisfying the conditions: