Bermutation

순열 $p$는 1부터 $n$까지의 정수로 이루어진다. 다음 연산을 원하는 만큼 적용할 수 있다. 연속한 $2b$개의 원소를 골라 두 절반을 서로 바꾼다. 구체적으로 $a_i, a_{i+1}, \ldots, a_{i+2b-1}$ 구간을 고르면 $a_{i+b}, a_{i+b+1}, \ldots, a_{i+2b-1}, a_i, a_{i+1}, \ldots, a_{i+b-1}$ 순서가 된다.

$p$에 이 연산을 0번 이상 적용해 얻을 수 있는 모든 순열의 집합을 $S$라 하자. 각 연산에서 구간은 다른 연산의 구간과 독립적으로 고를 수 있다. $S$의 모든 순열을 사전순으로 나열하고 1번부터 번호를 매긴다. $p$가 이 목록에서 몇 번째인지 구하라. 답은 $120\,586\,241$로 나눈 나머지로 출력한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 주어진다. 첫 줄에는 두 정수 $n$과 $b$가 주어진다 ($2 \le n \le 10^5$, $1 \le b$, $2b \le n$). 둘째 줄에는 순열 $p$의 원소 $n$개가 주어진다. 1부터 $n$까지의 각 정수는 정확히 한 번씩 나타난다.

모든 테스트 케이스의 $n$의 합은 $10^5$을 넘지 않는다.

각 테스트 케이스마다 $p$가 사전순으로 나열한 목록에서 몇 번째인지 1부터 세어 출력한다. 값은 $120\,586\,241$로 나눈 나머지이다.