Recently Arya the little panda got a permutation of size $A$ as a birthday present from his parents. Being a crazy little panda, he decided to make some operations on it. In each operation he chooses some index $i(1≤i≤n)$ and moves $A_i$ to the front of the permutation.
Let's say the initial permutation is ( 3, 5, 4, 1, 6, 2 ) and the sequence of operations is ( 3, 2, 5).
So after the 1st operation, the permutation becomes,
( 4, 3, 5, 1, 6, 2 )
After the 2nd operation, the permutation becomes,
( 3, 4, 5, 1, 6, 2 )
After the 3rd operation, the permutation becomes,
( 6, 3, 4, 5, 1, 2 )
Arya has the initial permutation and the final permutation, he also remembers how many operations were made but he forgot the sequence of operations. Now he wonders, how many sequence of operations could there be? As the number can be quite large, output it modulo 998244353.
First line of input consists of a single integer $T$, the number of test cases $(1 ≤ T ≤ 10)$
Each test case consists of two lines as follows :
First line of the test case contains $n$, the length of permutation and $m$, the length of operation sequence ($1 ≤ n, m ≤ 5000$).
Second line contains $n$ space-separated distinct integers, denoting the initial permutation $A$( $1≤ A_i ≤ n $).
Third line contains $n$ space-separated distinct integers, denoting the final permutation $B$( $1≤ B_i ≤ n $).
For each testcase print one integer, the possible number of operation sequences of length $m$ modulo 998244353 . Two sequences are considered different if there is atleast one index where they differ.
| Input | Output |
|---|---|
1 4 2 3 2 4 1 1 3 2 4 | 2 |
We call a sequence of integers $A$ permutation if every integer from $1$ to $|A|$ appears exactly once in the sequence, where $|A|$ denotes the length of the sequence.