Description

高级天花板制造商（ACM）正在分析其新系列的极其防坍塌天花板（ICPC）的特性。一个 ICPC 由 $n$ 层材料组成，每层都有不同的抗坍塌值（以正整数表示）。ACM 想要进行的分析将把各层的抗坍塌值存储在一个二叉搜索树中，并检查该树的形状是否与整个结构的质量相关。因为，为什么不呢？

具体来说，ACM 将从顶层到底层依次获取各层的抗坍塌值，并将它们逐一插入到树中。插入值 $v$ 的规则是：

如果树是空的，则将 $v$ 作为树的根。

如果树不为空，将 $v$ 与树的根进行比较。如果 $v$ 较小，则将 $v$ 插入到根的左子树中，否则插入到右子树中。

ACM 有一组天花板原型，它想通过尝试坍塌它们来进行分析。它想将具有相同树形状的天花板原型分组并一起分析。

例如，假设 ACM 正在考虑五个具有三层的天花板原型，如样例输入 1 所述并如图 1 所示。注意，第一个原型的顶层抗坍塌值为 2，中间层的值为 7，底层的值为 1。第二个原型的层的抗坍塌值为 3、1 和 4——然而这两个原型产生了相同的树形状，因此 ACM 将一起分析它们。

给定一组原型，您的任务是确定它们产生了多少种不同的树形状。

图 1：样例输入 1 中天花板原型所产生的四种树形状。

Input Format

输入的第一行包含两个整数 $n$ ($1 \le n \le 50$)，表示要分析的天花板原型的数量，以及 $k$ ($1 \le k \le 20$)，表示每个原型的层数。

接下来的 $n$ 行描述了天花板原型。每行包含 $k$ 个不同的整数（范围在 $1$ 到 $10^6$ 之间，包括边界），这些整数是天花板原型中各层的抗坍塌值，从上到下排列。

Output Format

输出不同树形状的数量。

5 3
2 7 1
3 1 4
1 5 9
2 6 5
9 7 3

4

3 4
3 1 2 40000
3 4 2 1
33 42 17 23

2

Hint

时间限制：5000 毫秒，内存限制：1048576 KB。

国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2016。

题面翻译由 ChatGPT-4o 提供。