AT_abc025_d [ABC025D] 25個の整数

高桥君打算在一个 $5$ 行 $5$ 列的棋盘上，将 $1$ 到 $25$ 的整数各写一次。 高桥君希望整数的摆放满足以下所有条件： - 每个格子分配一个整数。 - 无论在纵向或横向连续取出 $3$ 个整数，这 $3$ 个数都不会严格递增或严格递减。即，设从上到下第 $i$ 行，从左到右第 $j$ 列的格子中写的整数为 $n_{i,j}$，则需满足以下两个条件： - 不存在整数组 $(i,j)\ (1\leq i\leq 3,\ 1\leq j\leq 5)$，使得 $n_{i,j}n_{i+2,j}$。 - 不存在整数组 $(i,j)\ (1\leq i\leq 5,\ 1\leq j\leq 3)$，使得 $n_{i,j}n_{i,j+2}$。 部分格子的整数已经确定。你的任务是计算，满足上述条件的剩余整数的所有可能摆放方案数。

输入为如下形式，从标准输入读入。 > $x_{1,1}$ $x_{1,2}$ $x_{1,3}$ $x_{1,4}$ $x_{1,5}$ > $x_{2,1}$ $x_{2,2}$ $x_{2,3}$ $x_{2,4}$ $x_{2,5}$ > $x_{3,1}$ $x_{3,2}$ $x_{3,3}$ $x_{3,4}$ $x_{3,5}$ > $x_{4,1}$ $x_{4,2}$ $x_{4,3}$ $x_{4,4}$ $x_{4,5}$ > $x_{5,1}$ $x_{5,2}$ $x_{5,3}$ $x_{5,4}$ $x_{5,5}$ - 第 $1$ 行包含 $5$ 个整数 $x_{1,1}\ (0\leq x_{1,1}\leq 25)$、$x_{1,2}\ (0\leq x_{1,2}\leq 25)$、$x_{1,3}\ (0\leq x_{1,3}\leq 25)$、$x_{1,4}\ (0\leq x_{1,4}\leq 25)$、$x_{1,5}\ (0\leq x_{1,5}\leq 25)$，以空格分隔。 - 第 $2$ 行包含 $5$ 个整数 $x_{2,1}\ (0\leq x_{2,1}\leq 25)$、$x_{2,2}\ (0\leq x_{2,2}\leq 25)$、$x_{2,3}\ (0\leq x_{2,3}\leq 25)$、$x_{2,4}\ (0\leq x_{2,4}\leq 25)$、$x_{2,5}\ (0\leq x_{2,5}\leq 25)$，以空格分隔。 - 第 $3$ 行包含 $5$ 个整数 $x_{3,1}\ (0\leq x_{3,1}\leq 25)$、$x_{3,2}\ (0\leq x_{3,2}\leq 25)$、$x_{3,3}\ (0\leq x_{3,3}\leq 25)$、$x_{3,4}\ (0\leq x_{3,4}\leq 25)$、$x_{3,5}\ (0\leq x_{3,5}\leq 25)$，以空格分隔。 - 第 $4$ 行包含 $5$ 个整数 $x_{4,1}\ (0\leq x_{4,1}\leq 25)$、$x_{4,2}\ (0\leq x_{4,2}\leq 25)$、$x_{4,3}\ (0\leq x_{4,3}\leq 25)$、$x_{4,4}\ (0\leq x_{4,4}\leq 25)$、$x_{4,5}\ (0\leq x_{4,5}\leq 25)$，以空格分隔。 - 第 $5$ 行包含 $5$ 个整数 $x_{5,1}\ (0\leq x_{5,1}\leq 25)$、$x_{5,2}\ (0\leq x_{5,2}\leq 25)$、$x_{5,3}\ (0\leq x_{5,3}\leq 25)$、$x_{5,4}\ (0\leq x_{5,4}\leq 25)$、$x_{5,5}\ (0\leq x_{5,5}\leq 25)$，以空格分隔。 上述 $25$ 个整数表示如下信息： - 整数 $x_{i,j}\ (1\leq i\leq 5,\ 1\leq j\leq 5)$ 表示从上到下第 $i$ 行，从左到右第 $j$ 列的格子中写的整数。若 $x_{i,j}=0$，表示该格子的整数未确定；若 $x_{i,j}\neq 0$，则该格子的整数为 $x_{i,j}$。 此外，输入保证以下条件： - 对于 $1\leq i,k\leq 5,\ 1\leq j,l\leq 5$，若 $x_{i,j}\geq 1$ 且 $x_{k,l}\geq 1$ 且 $(i,j)\neq (k,l)$，则 $x_{i,j}\neq x_{k,l}$。 - 满足 $x_{i,j}\neq 0$ 的格子 $(i,j)$ 至少有 $5$ 个。

输出满足条件的剩余整数的所有可能摆放方案数，对 $1000000007\ (=1,000,000,007)$ 取模。输出末尾需换行。

## 部分分 本题设有部分分。 - 数据集 $1$：所有输入中，满足 $x_{i,j}\neq 0$ 的格子 $(i,j)$ 至少有 $17$ 个。通过数据集 $1$ 可得 $30$ 分。 - 数据集 $2$：无额外限制，通过数据集 $2$ 可得 $70$ 分。 ## 样例说明 1 - 还未填写的整数为 $6,\ 11,\ 12,\ 13,\ 14,\ 24$ 共 $6$ 个。以下 $2$ 种方案满足条件。 14121527131116122202541963239181017245218 14131527121116122202541963239181017245218 ## 样例说明 2 - 无论如何填写剩余的数都能满足条件。 ## 样例说明 3 - 有时无论如何填写都无法满足条件。 ## 样例说明 4 - 若所有整数的位置都已确定，也需输出方案数。 由 ChatGPT 4.1 翻译