Laska 是厕所之王的儿子。作为如此重要人物的儿子，他承受了巨大的压力，因此他决定问自己一个真正重要的问题——我这辈子到底想做什么？他给自己的答案是，他想一直处于兴奋（high）的状态。

在兴奋的状态下，他看到了关于排列的奇妙幻象。它们呈现出不同的形状和图案。在这些无限交织的排列中，他能够分辨出 $n$ 个由整数 $1, 2, \dots, m$ 组成的排列。

他选择了其中一个排列，记为 $\pi_1, \pi_2, \dots, \pi_m$。他根据以下算法基于该排列创建了一个新的排列：

• 从空序列开始。
• 按 $1, 2, \dots, m$ 的顺序分析元素。对于元素 $\pi_i$，他将其添加到当前序列的开头或末尾。

例如，如果初始排列为 $(5, 2, 3, 1, 4)$，他可以创建排列 $() \to (5) \to (2, 5) \to (3, 2, 5) \to (3, 2, 5, 1) \to (4, 3, 2, 5, 1)$。

他对他的每个初始排列都恰好执行了一次此操作。令人惊讶的是，所有生成的最终排列都是相同的。

第二天他把这个故事告诉了你。现在你想知道有多少种不同的排列可以通过这种方式创建。此外，你还想恢复可以通过这种方式创建的字典序最小的可能排列（如果存在的话）。

提示：如果存在一个索引 $k$ 满足 $a_k < b_k$ 且对于 $1 \le i < k$ 有 $a_i = b_i$，则排列 $a_1, a_2, \dots, a_m$ 在字典序上小于排列 $b_1, b_2, \dots, b_m$。

输入格式

第一行给出一个整数 $Z \le 50$，表示接下来描述的测试用例数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示排列的数量和这些排列的长度。

接下来的 $n$ 行中，每行包含对这些排列之一的描述。一个排列的描述由集合 $\{1, 2, \dots, m\}$ 中的 $m$ 个两两不同的整数组成。

$n, m \in [1, 1000]$，所有测试用例的 $n$ 之和不超过 $5\,000$。

输出格式

对于每个测试用例，你的程序应该在第一行输出可以被创建的排列数量模 $10^9 + 7$ 的余数。

如果存在至少一个这样的排列，则在第二行中，你应该以与输入相同的格式输出其中字典序最小的排列。

如果不存在这样的排列，则只需输出一行。

样例

输入样例 1

4
1 5
1 2 3 4 5
2 5
1 2 5 4 3
5 2 1 4 3
2 5
1 2 3 4 5
5 4 3 2 1
3 5
1 2 3 4 5
1 3 5 2 4
3 4 2 1 5

输出样例 1

16
1 2 3 4 5
8
1 2 5 4 3
2
1 2 3 4 5
0