L - Unique Sheet 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

N \times N のグリッドがあります。それぞれのマスには 1 つずつ整数が書かれており、マス (i, j) には A_{i,j}（1 \le A_{i,j} \le (N - K)^2）が書かれています。

パンダのパ太郎はこのグリッドに対して次のような操作を行いました。

  • N 行の中から K 個の行を選び、これらを削除する。
  • N 列の中から K 個の列を選び、これらを削除する。

操作を行った結果、残った (N - K)^2 個の数字がすべて異なるものだったと言います。

パ太郎が行った操作として考えられるものの通り数を 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