题目描述

给定一个 $N \times N$ 的矩阵和一个整数 $K$。该矩阵的第 $i$ 行第 $j$ 列的元素为 $a_{i,j}$。这个矩阵包含了 $1, 2, \dots, N^2$ 的所有数，每个数恰好出现一次。

sigma 君可以按任意顺序、任意次数进行以下两种操作：

• 对于所有 $i$（$1 \leq i \leq N$），如果存在 $x, y$（$1 \leq x < y \leq N$）使得 $a_{i,x} + a_{i,y} \leq K$，则可以交换矩阵的第 $x$ 列和第 $y$ 列。
• 对于所有 $i$（$1 \leq i \leq N$），如果存在 $x, y$（$1 \leq x < y \leq N$）使得 $a_{x,i} + a_{y,i} \leq K$，则可以交换矩阵的第 $x$ 行和第 $y$ 行。

问最终能够得到多少种不同的矩阵？请输出答案对 $998244353$ 取模后的结果。

输入格式

输入以如下格式从标准输入读入：

$N$ $K$ $a_{1,1}$ $a_{1,2}$ $\dots$ $a_{1,N}$ $a_{2,1}$ $a_{2,2}$ $\dots$ $a_{2,N}$ $\dots$ $a_{N,1}$ $a_{N,2}$ $\dots$ $a_{N,N}$

输出格式

输出最终能够得到的不同矩阵的种数，对 $998244353$ 取模。

样例 1

输入

3 13
3 2 7
4 8 9
1 6 5

输出

12

样例 2

输入

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 2N^2$
• $a_{i,j}$ 是 $1, 2, \dots, N^2$ 的一个排列
• 输入的所有数均为整数

样例解释 1

例如，可以选择 $x=1, y=2$ 交换列向量，得到如下矩阵：

2 3 7
8 4 9
6 1 5

之后再选择 $x=1, y=3$ 交换行向量，得到如下矩阵：

6 1 5
8 4 9
2 3 7

由 ChatGPT 4.1 翻译