Cyclic shifts in permutation

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian
You have a permutation P of integers 1, 2, ... , N. You want to change it a little. To do this, you choose an integer K that satisfies an inequality 2 ≤ K ≤ N. After that, you perform several (possibly, zero, if you're feeling lazy) cyclic shifts. For each cyclic shift you choose a Klength segment of the permutation P (let's denote it as P_{x}, P_{x + 1}, ..., P_{x + K  2}, P_{x + K  1}) and perform a cyclic shift on it towards the right. That is, rearrange elements of this segment in the order P_{x + K  1}, P_{x}, ... , P_{x + K  3}, P_{x + K  2}.
For example, let's make a permutation (6, 5, 1, 3, 2, 4) from permutation (1, 5, 4, 6, 3, 2), using K = 4. Segments that are cyclically shifted on every move are underlined: (1, 5, 4, 6, 3, 2) => (6, 1, 5, 4, 3, 2)=> (6, 1, 2, 5, 4, 3) => (6, 1, 3, 2, 5, 4) => (6, 5, 1, 3, 2, 4).
Let S denote the set of permutations that can be obtained from permutation P using zero or more cyclic shifts. You are given a permutation Q of integers 1, 2, ..., N. Your task is to find whether S contains Q or not. If so, also you must find the index of Q in the list of all permutations in set S, ordered lexicographically.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N and K denoting the length of the permutations P and Q, and length of the segments that you are allowed to cyclically shift.
Next line contains N integers P_{1}, P_{2}, ..., P_{N} denoting the permutation P.
Next line contains N integers Q_{1}, Q_{2}, ..., Q_{N} denoting the permutation Q.
Output
For each test case, output a single line. It must contain 1, if permutation Q can't be obtained from permutation P using allowed cyclic shifts. Otherwise, print its 1based index in the list of all permutations from set S, ordered lexicographically. Since the answer can be very large, print it modulo 10^{9} + 7.
Constraints
 2 ≤ N ≤ 10^{5}
 2 ≤ K ≤ N
 P_{1}, P_{2}, ..., P_{N} are forming a permutation of integers from 1 to N
 Q_{1}, Q_{2}, ..., Q_{N} are forming a permutation of integers from 1 to N
Subtasks
Subtask 1: (10 points)
 1 ≤ T ≤ 1000
 2 ≤ N ≤ 5
Subtask 2: (10 points)
 1 ≤ T ≤ 10
 2 ≤ N ≤ 10^{5}
 K = N
Subtask 3: (40 points)
 1 ≤ T ≤ 10
 2 ≤ N ≤ 1000
Subtask 4: (40 points)
 1 ≤ T ≤ 10
 Original constraints
Example
Input: 2 4 2 2 4 3 1 1 2 4 3 3 3 1 2 3 1 3 2 Output: 2 1
Explanation
Example case 1. Cyclic shift of segment of length 2 is swapping consecutive elements of the permutation. Using them, we are able to get any possible permutation. Permutation Q has index 2 in the list of all permutations of length 4.
Example case 2. We are able to get permutations (1, 2, 3), (2, 3, 1) and (3, 1, 2). Permutation Q doesn't belong to this list, so answer is 1.
Author:  eartemov 
Editorial  http://discuss.codechef.com/problems/PERSHFTS 
Tags  eartemov, fenwicktree, inversions, maths, medium, oct15, permutation 
Date Added:  4082015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions