#P18034. Unique Sheet

Unique Sheet

Unique Sheet

给定一个 N×NN\times N 的整数表格,其中每个数都在 11 到 (N−K)2(N-K)^2 之间。

先选择并删除恰好 KK 行,再选择并删除恰好 KK 列。求有多少种选择方式,使剩余 (N−K)×(N−K)(N-K)\times(N-K) 个数两两不同。答案对 998244353998244353 取模。

一种方式由选中的行集合和列集合决定,删除同一个集合内各行、各列的先后顺序不计入方案数。

输入格式

第一行两个整数 N,KN,K。接下来 NN 行,每行 NN 个整数,表示表格。

输出格式

输出一个整数,表示满足条件的方式数量对 998244353998244353 取模的结果。

数据范围

2≤N≤10002\le N\le1000,1≤K≤51\le K\le5,K<NK<N,1≤Ai,j≤(N−K)21\le A_{i,j}\le(N-K)^2。所有输入均为整数。

样例说明

第一组可删除的(行号,列号)分别为 (1,1),(1,3),(2,1),(2,2),(3,2),(3,3)(1,1),(1,3),(2,1),(2,2),(3,2),(3,3),共 66 种。

样例 1

输入:

3 1
1 2 4
3 4 2
2 1 3

输出:

6

样例 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

输出:

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

输出:

36