19190번 - Bermutation 다국어

문제

Your are given a permutation $p$ of integers from 1ドル$ to $n$. You are allowed to modify this permutation in the following way: choose a segment of 2ドル b$ consecutive elements and swap the halves of this segment. Formally, if you choose the segment $a_{i}, a_{i + 1} \ldots, a_{i + 2 b - 1},ドル you will get $a_{i + b}, a_{i + b + 1}, \ldots, a_{i + 2 b - 1}, a_{i}, a_{i + 1}, \ldots, a_{i + b - 1}$ after swapping its halves.

Consider the set $S$ of all permutations which can be obtained from the given permutation $p$ by applying this modification zero or more times. The segment of 2ドル b$ consecutive elements for each modification can be chosen independently of the segments chosen for other modifications. List all these permutations in lexicographical order and enumerate them starting from 1ドル$. Your task is to find the number of $p$ itself in this ordered list. Print the answer modulo 120ドル,586円,241円$.

입력

The first line of input contains one positive integer $T,ドル the number of test cases. The test cases follow.

Each test case is given on two lines. The first line contains with two integers $n$ and $b$ (2ドル \le n \le 10^5,ドル 1ドル \le b$ and 2ドル b \le n$). The second line of each test case contains $n$ integers: the permutation $p$. Each integer from 1ドル$ to $n$ appears on this line exactly once.

The sum of all $n$ in the input does not exceed 10ドル^5$.

출력

Print the 1ドル$-based number of permutation $p$ in the lexicographically ordered list of all permutations which can be obtained by the described modifications, modulo 120ドル,586円,241円$.

제한

힌트