410674: GYM104072 L Windfield

Bibita found a windfield shaped like an $$$N \times N$$$ matrix. There are very strong winds in the windfield. Anything in cell $$$(i,j)$$$ ($$$0 \le i, j < N$$$) would move after one second to one of the adjacent cells, with a given probability. If the winds are not strong enough, it will stay in the same cell.

Bibita likes odd and even numbers. She throws an object (could be anything) in the windfield, which will fall randomly in one of the cells at second $$$0$$$. She now wonders what is the probability that after $$$K$$$ seconds, the object will be on a cell $$$(i, j)$$$ where $$$j$$$ has the same parity as $$$K$$$. Can you help her find this answer?

Bibita considers that the coordinats in the windfield are 0 indexed (eg. the first cell (0, 0) is on an even column).

The first line of the input contains an integer $$$N$$$ ($$$2 \leq N \leq 500$$$), denoting the size of the windield matrix.

On each of the following $$$N \times N$$$ lines you'll be given at least $$$3$$$ and at most $$$5$$$ integers $$$a_p$$$ ($$$0 \le a_p < 998244353$$$), denoting the probabilities for the $$$ith$$$ cell in the matrix (numbered from top left to bottom right).

For a cell having all $$$4$$$ neighbours you will be given $$$5$$$ values $$$a_s$$$, $$$a_t$$$, $$$a_r$$$, $$$a_b$$$, $$$a_l$$$ corresponding in this order to the probability of: staying in the same cell, moving up, moving right, moving down, moving left. If the cell is a corner or an edge, the missing neighbours are omitted (eg. for the top-left corner you'll be given only $$$a_s$$$, $$$a_r$$$, $$$a_b$$$). The probability is a fraction $$$\frac{a}{b}$$$ given as $$$a \times b^{−1}$$$ (modulo $$$998244353$$$), where $$$b^{−1}$$$ is the modular inverse of $$$b$$$ modulo $$$998244353$$$.

The next line contains an integer $$$Q$$$ ($$$1 \le q \le 10^3$$$), denoting the number of testcases.

Each of the following $$$Q$$$ lines contain an integer $$$K$$$ ($$$1 \le K \le 10^9$$$).

It is guaranteed that for $$$N > 10$$$, $$$N^2 \times K \le 2 \times 10^6$$$

You should output the result for each of the $$$Q$$$ question, modulo $$$998244353$$$, on a separate line.

2
489139733 389315298 119789323
768648152 109806879 119789323
658841273 559016838 778630596
958314579 708753491 329420637
2
31
19

888372042
963737898