配点 : 100 点
問題文
N \times N 网格。每个方格中写入一个整数,并且该方格 (i, j) 有 直到 A_{i,j}(1 \le A_{i,j} \le (N - K)^2)被写入。
熊猫 Pataro 在此网格上执行了以下操作。
- N 从行内 选择 K 行并删除它们。
- N 从栏内 选择 K 列并将其删除。
操作结果是,剩余的 假设 (N - K)^2 数字全部不同。
计算 Pataro 执行的可能操作。 998244353 除的余数。
但是, 运算前设定中包含的2 两个操作是不同的。 2 当且仅当在两个操作中的至少一个操作中选择的行集或列集不同时。
制約
- 1 \le K < N \le 1000
- K \le 5
- 1 \leq A_{i,j} \leq (N-K)^2
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N K
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}
出力
答案 请打印除以 1 行输出。
入力例 1
3 1 1 2 4 3 4 2 2 1 3
出力例 1
6
下一步 6 以下操作方法满足条件。通过执行这些操作中的每一个,剩余的 (N-K)^2 数字按降序排列 1,2,3,4 。 对于
- 1 在第二次操作中 1 选择行,2 在第二次操作中 1 选择列。
- 1 在第二次操作中 1 选择行,2 在第二次操作中 3 选择列。
- 1 在第二次操作中 2 选择行,2 在第二次操作中 1 选择列。
- 1 在第二次操作中 2 选择行,2 在第二次操作中 2 选择列。
- 1 在第二次操作中 3 选择行,2 在第二次操作中 2 选择列。
- 1 在第二次操作中 3 选择行,2 在第二次操作中 3 选择列。
入力例 2
6 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例 2
36
入力例 3
7 5 2 3 1 4 1 3 1 4 4 1 4 1 1 1 1 3 4 1 4 3 4 4 2 2 2 1 2 2 2 4 1 4 2 3 1 2 3 1 3 1 2 4 3 3 2 1 4 2 2
出力例 3
36