시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 0 0 0 0.000%

문제

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$.

예제 입력 1

2
5 1
2 3 1 4 5
5 2
2 3 1 4 5

예제 출력 1

31
3