SRTMACH  Sorting Machine
Once upon a time, there was a machine, a sorting machine called Conchita, she was not very efficient, most of the times she even couldn't sort the data correctly, and she only could process a list of $2 \le N \le 10$ numbers, her algorithm was the following, she was programmed with 2 permutations of $N$ numbers, each permutation $F$ is given by $N$ numbers, $f_1, f_2, \ldots, f_N$, such that $1 \le f_i \le N$, $f_i \ne f_j$ for $i \ne j$ and means that if she apply $F$ to the given list, she gets a list where the $f_i$ element, corresponds to the $i$ element on the original list, then she forms a set of rearrangements of the original list, applying any of these permutations any number of times, in any order to the given list, so she forms all possible rearrangements using the given permutations, then she chooses to output the one that minimize the first element, if there is any tie, she chooses the one that minimize the second element and if there is any tie, she looks at the third element, and so on...
Her creator, a robot called Robotina, was very curious about Conchita's behavior, she chooses an integer $1 \le M \le 10$, an then she tries all possible lists, $a_1, a_2, \ldots, a_N$, such that $1 \le a_i \le M$, and then for each input, she sends it to Conchita, and receives an output, then she asks herself, how many possible different outputs does Conchita can compute? (Two outputs are considered different if at least one element differs).
Your task, find this number MOD $98765431$.
Input
The first line of input contains an integer $T \le 10$, the number of test cases. It is followed by $T$ test cases, the first line of each test case contains 2 integer numbers, $N$, $M$, then is followed by 2 lines, each one consisting on $N$ numbers.
Output
For each case, output a single line consisting of the number of different outputs MOD $98765431$.
Input Sample
2 2 2 1 2 2 1 3 3 2 1 3 3 1 2
Output sample
3 10
hide comments
khanhtai:
20240226 14:58:01
can someone tell me how to solve this problem? 

Min_25:
20151211 09:28:47
I assumed that (list) ∈ [1, M]^n.


Bjarki Ágúst Guðmundsson:
20151014 04:27:22
The problem description is pretty hard to understand. Here are a few clarifications:


Narendra yadav:
20130407 16:09:26
Pl explain the cases.


Jared Deckard:
20120214 20:36:37
messy...


manowar:
20120208 15:53:39
K is a mistake, K =2 should be read 

Suit up!:
20120208 15:06:05
What is K in the input description? 
Added by:  Paulo Costa 
Date:  20120130 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  UGTO 