Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Caching Combinatorics

By Arghya · Limits 2s, 512 MB

Recently Arya the little panda got a permutation of size AA 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(1in)i(1≤i≤n) and moves AiA_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 TT, the number of test cases (1T10)(1 ≤ T ≤ 10)
Each test case consists of two lines as follows :
First line of the test case contains nn, the length of permutation and mm, the length of operation sequence (1n,m50001 ≤ n, m ≤ 5000).
Second line contains nn space-separated distinct integers, denoting the initial permutation AA( 1Ain1≤ A_i ≤ n ).
Third line contains nn space-separated distinct integers, denoting the final permutation BB( 1Bin1≤ B_i ≤ n ).


For each testcase print one integer, the possible number of operation sequences of length mm modulo 998244353 . Two sequences are considered different if there is atleast one index where they differ.


4 2
3 2 4 1
1 3 2 4

We call a sequence of integers AA permutation if every integer from 11 to A|A| appears exactly once in the sequence, where A|A| denotes the length of the sequence.



    0% Solution Ratio


    Login to submit