408095: GYM102984 K Determinant

The determinant is one of the important objects covered in linear algebra.

For a natural number $$$n$$$, $$$S_n$$$ is the set of all permutations: functions from $$$\{1, 2, \ldots, n\}$$$ to $$$\{1, 2, \ldots, n\}$$$ such that all $$$n$$$ values $$$f(1), f(2), \ldots, f(n)$$$ are different.

For $$$f \in S_n$$$, $$$\mathit{inv}(f)$$$ is the number of inversions in permutation $$$f$$$: the number of pairs $$$(i, j)$$$ such that $$$i < j$$$ but $$$f(i) > f(j)$$$.

Consider matrix $$$A$$$ of size $$$N \times N$$$. Let $$$a_{i,j}$$$ be the element at row $$$i$$$ and column $$$j$$$. The determinant of $$$A$$$ is:

$$$$$$ \det(A) = \sum\limits_{f \in S_n}(-1)^{\mathit{inv}(f)} \prod\limits_{i=1}^{n} a_{i,f(i)}\text{.} $$$$$$

We have an $$$N \times N$$$ matrix $$$A$$$ where each element is an integer. Let's run $$$Q$$$ of the following queries.

When the integer $$$x$$$ is given, print the value of the determinant of $$$A - x I$$$, where $$$I$$$ is an $$$N \times N$$$ unit matrix.

Since the value can be too large, print the answer modulo prime number $$$998\,244\,353$$$.

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N \le 500$$$, $$$1 \le Q \le 250\,000$$$).

The next $$$N$$$ lines describe matrix $$$A$$$. The $$$i$$$-th of these lines contains $$$N$$$ integers, and the $$$j$$$-th of these integers represents $$$a_{i,j}$$$ ($$$0 \le a_{i,j} < 998\,244\,353$$$).

Then $$$Q$$$ lines follow, each containing one query: an integer $$$x$$$ ($$$0 \le x < 998\,244\,353$$$).

For each query, print the answer on a separate line.

3 6
2 4 5
6 3 8
1 6 3
10 9 5 8 3 1

407 470 402 495 260 110