K - Lucky Grid Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

問題文

各マスに数が書かれた 4 行 4 列のグリッドについて考えます。 上から i 行目、左から j 列目のマスを (i,j) とし、そこに書かれた数を a_{i,j} とします。 このとき、このグリッドが良いグリッドであるとは以下の条件が共に満たされることをいいます：

  • 各行に書かれた数が左から右に狭義単調増加している。すなわち、すべての i,j\ (1\leq i\leq N, 1\leq j< N) について a_{i,j} < a_{i,j+1}
  • 各列に書かれた数が上から下に狭義単調増加している。すなわち、すべての i,j\ (1\leq i< N, 1\leq j\leq N) について a_{i,j} < a_{i+1,j}

各 1\leq i,j\leq 4 に対して整数 A_{i,j} が与えられます。 以下の条件を共に満たす良いグリッドの数を 998244353 で割った余りを求めてください。

  • 各マスには 1 以上 M 以下の整数が書かれている
  • 各 1\leq i,j\leq 4 に対し、A_{i,j}\neq -1 ならばマス (i,j) には A_{i,j} が書かれている

制約

  • 1\leq M \leq 30
  • A_{i,j}=-1 または 1\leq A_{i,j}\leq M
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

M
A_{1,1} A_{1,2} A_{1,3} A_{1,4}
A_{2,1} A_{2,2} A_{2,3} A_{2,4}
A_{3,1} A_{3,2} A_{3,3} A_{3,4}
A_{4,1} A_{4,2} A_{4,3} A_{4,4}

出力

条件を満たす良いグリッドの数を 998244353 で割った余りを出力せよ。

入力例 1

10
1 2 3 4
2 -1 -1 5
3 -1 -1 7
4 5 8 9

出力例 1

2

条件を満たすグリッドは以下の 2 通りです。

1 2 3 4
2 3 4 5
3 4 5 7
4 5 8 9

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

入力例 2

30
1 1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

出力例 2

0

入力例 3

21
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

出力例 3

248851853

998244353 で割った余りを求めることに注意してください。

Problem Statement

Consider a 4\times 4 grid with a number written on each cell. Let (i,j) be the cell in the i-th row from the top and j-th column from the left, and a_{i,j} be the number written on it. We say this grid is good if both of the following conditions are met:

  • The numbers written on each row increase strictly monotonically from left to right. That is, a_{i,j} < a_{i,j+1} for all i,j\ (1\leq i\leq N, 1\leq j< N).
  • The numbers written on each column increase strictly monotonically from top to bottom. That is, a_{i,j} < a_{i+1,j} for all i,j\ (1\leq i< N, 1\leq j\leq N).

You are given an integer A_{i,j} for each 1\leq i,j\leq 4. Find the number, modulo 998244353, of good grids such that:

  • an integer between 1 and M, inclusive, is written on each cell, and
  • for 1\leq i,j\leq 4, if A_{i,j}\neq -1, then A_{i,j} is written on cell (i,j).

Constraints

  • 1\leq M \leq 30
  • A_{i,j}=-1 or 1\leq A_{i,j}\leq M.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

M
A_{1,1} A_{1,2} A_{1,3} A_{1,4}
A_{2,1} A_{2,2} A_{2,3} A_{2,4}
A_{3,1} A_{3,2} A_{3,3} A_{3,4}
A_{4,1} A_{4,2} A_{4,3} A_{4,4}

Output

Print the number, modulo 998244353, of good grids that satisfy the conditions.

Sample Input 1

10
1 2 3 4
2 -1 -1 5
3 -1 -1 7
4 5 8 9

Sample Output 1

2

Two grids satisfy the conditions:

1 2 3 4
2 3 4 5
3 4 5 7
4 5 8 9

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

Sample Input 2

30
1 1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

Sample Output 2

0

Sample Input 3

21
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

Sample Output 3

248851853

Be sure to find the count modulo 998244353.