题目描述

$N\ \times\ N$ の行列と、整数 $K$ が与えられます。この行列の $i$ 行目、$j$ 列目の値を $a_{i,\ j}$ とします。この行列は、 $1,\ 2,\ \dots,\ N^2$ をちょうど一つずつ要素に含みます。

sigma くんは、以下の $2$ 種類の操作を、好きな順序で 好きな回数 行えます。

• 全ての $i$ ($1\ \leq\ i\ \leq\ N$) について $a_{i,\ x}\ +\ a_{i,\ y}\ \leq\ K$ を満たす $x,\ y(1\ \leq\ x\ <\ y\ \leq\ N)$ を選び、行列の $x,\ y$ 列目をswapする。
• 全ての $i$ ($1\ \leq\ i\ \leq\ N$) について $a_{x,\ i}\ +\ a_{y,\ i}\ \leq\ K$ を満たす $x,\ y(1\ \leq\ x\ <\ y\ \leq\ N)$ を選び、行列の $x,\ y$ 行目をswapする。

最終的に得られる行列は何種類存在するでしょうか？ $\bmod\ 998244353$ で答えてください。

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $K$ $a_{1,\ 1}$ $a_{1,\ 2}$ $...$ $a_{1,\ N}$ $a_{2,\ 1}$ $a_{2,\ 2}$ $...$ $a_{2,\ N}$ $:$ $a_{N,\ 1}$ $a_{N,\ 2}$ $...$ $a_{N,\ N}$

输出格式

最終的に得られる行列が何種類存在するかを $\bmod\ 998244353$ で出力せよ。

题目大意

给定一个 $N \times N$ 的矩阵，其中元素为 $1, 2 ... N^2$

可以选择对所有 $x \in [1, n]$ 满足 $a_{i, x}+a_{j, x} <= k$ 的两行 $i, j$ 进行交换

可以选择对所有 $x \in [1, n]$ 满足 $a_{x, i}+a_{x, j} <= k$ 的两列 $i, j$ 进行交换

问最终能得到多少种不同的矩阵

3 13
3 2 7
4 8 9
1 6 5

12

10 165
82 94 21 65 28 22 61 80 81 79
93 35 59 85 96 1 78 72 43 5
12 15 97 49 69 53 18 73 6 58
60 14 23 19 44 99 64 17 29 67
24 39 56 92 88 7 48 75 36 91
74 16 26 10 40 63 45 76 86 3
9 66 42 84 38 51 25 2 33 41
87 54 57 62 47 31 68 11 83 8
46 27 55 70 52 98 20 77 89 34
32 71 30 50 90 4 37 95 13 100

348179577

提示

制約

• $1\ \leq\ N\ \leq\ 50$
• $1\ \leq\ K\ \leq\ 2\ \times\ N^2$
• $a_{i,\ j}$ は $1,\ 2,\ \dots,\ N^2$ の並び替え
• 入力される数は全て整数である。

Sample Explanation 1

例えば $x\ =\ 1,\ y\ =\ 2$ として列ベクトルを swap でき、以下のようになります。 2 3 7 8 4 9 6 1 5 その後更に $x\ =\ 1,\ y\ =\ 3$ として行ベクトルを swap でき、以下のようになります。 6 1 5 8 4 9 2 3 7