← 返回题目列表

AtCoder · past20_k

K. 好格子

中文机器翻译题面 查看原题

问题陈述

考虑 4\times 4 网格,每个单元格上都写有数字。 让 (i,j) 是 i从顶部开始的第行和 j左起第 列,以及 a_{i,j} 是上面写的数字。 我们说这个网格是 好 如果满足以下两个条件:

  • 每行写入的数字从左到右严格单调增加。也就是说, a_{i,j} < a_{i,j+1} 对于所有人 i,j\ (1\leq i\leq N, 1\leq j< N).
  • 每列上写的数字从上到下严格单调递增。也就是说, a_{i,j} < a_{i+1,j} 对于所有人 i,j\ (1\leq i< N, 1\leq j\leq N).

给你一个整数 A_{i,j} 对于每个 1\leq i,j\leq 4。 求模数 998244353,良好的网格使得:

  • 之间的整数 1 和 M,包含在内,写在每个单元格上,并且
  • 为 1\leq i,j\leq 4,如果 单元格上写有 A_{i,j}\neq -1,那么 A_{i,j} 写在单元格上 (i,j).

约束

  • 1\leq M \leq 30
  • A_{i,j}=-1 or 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

两个格子满足条件:

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.