SP10510 SRTMACH - Sorting Machine

从前，有一台名为 Conchita 的排序机器。这个机器并不高效，通常情况下，它甚至无法正确排序数据。Conchita 只能处理长度为 $2 \le N \le 10$ 的数列。她的工作原理是：她接受了两个长度为 $N$ 的排列 $F$ 和 $G$，每个排列由 $N$ 个不同的数字 $f_1, f_2, \ldots, f_N$ 组成，满足 $1 \le f_i \le N$ 且 $f_i \ne f_j$ (对于 $i \ne j$)。这意味着当她将排列 $F$ 应用于给定的序列时，得到的新序列中第 $f_i$ 个位置的元素来自原序列的第 $i$ 个位置。 Conchita 可以通过对原列表应用这两个排列，任意次数和顺序，生成所有可能的重新排列，然后她总是选择第一个元素尽可能小的排列输出。如果有多个排列这样做，她会选择第二个元素最小的，依此类推。 她的创造者 Robotina 对 Conchita 的行为充满好奇。她选择一个整数 $1 \le M \le 10$，然后测试所有可能的数列 $a_1, a_2, \ldots, a_N$，使得 $1 \le a_i \le M$。对于每个可能的输入，Robotina 将其输给 Conchita，并记录下输出。她想知道，Conchita 能生成多少种不同的输出（如果输出有任何一个元素不同，则视为不同）。 你的任务是计算出不同输出的数量，并对 $98765431$ 取模。

第一行输入一个整数 $T \le 10$，代表测试用例的数量。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $M$，接下来两行，每行包含 $N$ 个数，表示两个排列。

对于每个测试用例，输出一行，表示不同输出的数量对 $98765431$ 取模的结果。 #### 输入样例 ``` 2 2 2 1 2 2 1 3 3 2 1 3 3 1 2 ``` #### 输出样例 ``` 3 10 ``` **本翻译由 AI 自动生成**