H. Games on the Ads 2: Painting
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Tired of those fake games on advertisements? Now try this one!

You are given an $$$n \times n$$$ grid. For each row and each column, there's a painting brush associated with it, totally $$$2n$$$ brushes. When you choose to use a brush, it will paint every cell in its corresponding row (or column) to the brush's designated color. In the game, there are $$$n$$$ colors numbered from $$$1$$$ to $$$n$$$. The designated colors of brushes corresponding to the rows form a permutation of $$$[1,2,\ldots,n]$$$. Similarly, the colors of brushes corresponding to the columns form a permutation of $$$[1,2,\ldots,n]$$$.

Brushes and the goal pattern of the example

The grid is initially empty with no color in any cell. The goal of the game is to paint the grid into the given pattern.

You are not satisfied with determining whether the goal can be achieved. You want to know, if you use each brush to paint exactly once, out of all $$$(2n)!$$$ possibilities, how many of them result in the goal pattern? Since the answer could be large, output it modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$n$$$ ($$$1\le n \le 20$$$), denoting the size of the grid.

The second line contains $$$n$$$ integers $$$p_1,p_2,\cdots,p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ denotes the color of the brush corresponding to the $$$i$$$-th row. It is guaranteed that $$$p$$$ is a permutation of $$$[1,2,\ldots,n]$$$.

The third line contains $$$n$$$ integers $$$q_1,q_2,\cdots,q_n$$$ ($$$1 \le q_i \le n$$$), where $$$q_i$$$ denotes the color of the brush corresponding to the $$$i$$$-th column. It is guaranteed that $$$q$$$ is a permutation of $$$[1,2,\ldots,n]$$$.

The following $$$n$$$ lines each contains $$$n$$$ integers, denoting an $$$n \times n$$$ matrix $$$c$$$ ($$$1 \le c_{i,j} \le n$$$), where $$$c_{i,j}$$$ denotes the color of the cell in the $$$i$$$-th row and $$$j$$$-th column of the goal pattern.

Output

Output a single integer, denoting the number of solutions modulo $$$998\,244\,353$$$.

Example
Input
2
1 2
1 2
1 1
2 2
Output
6
Note

For the example, if we number the $$$4$$$ brushes from top to bottom and then from left to right, the $$$6$$$ ways of the order to achieve the goal pattern are as follows.

  • $$$3,2,4,1$$$
  • $$$3,4,1,2$$$
  • $$$3,4,2,1$$$
  • $$$4,1,3,2$$$
  • $$$4,3,1,2$$$
  • $$$4,3,2,1$$$