给定一个从 $1$ 到 $n$ 的整数排列 $p$。你可以通过以下方式修改该排列：选择一个长度为 $2b$ 的连续段，并交换该段的前后两半。形式化地，如果你选择了段 $a_i, a_{i+1}, \dots, a_{i+2b-1}$，交换其两半后，你将得到 $a_{i+b}, a_{i+b+1}, \dots, a_{i+2b-1}, a_i, a_{i+1}, \dots, a_{i+b-1}$。

考虑由给定排列 $p$ 通过零次或多次上述修改所能得到的所有排列构成的集合 $S$。每次修改时，长度为 $2b$ 的连续段的选择是相互独立的。将这些排列按字典序排列并从 $1$ 开始编号。你的任务是求出排列 $p$ 本身在这个有序列表中的编号。请输出答案对 $120\,586\,241$ 取模的结果。

输入格式

输入的第一行包含一个正整数 $T$，表示测试用例的数量。接下来是各测试用例。 每个测试用例占两行。第一行包含两个整数 $n$ 和 $b$ ($2 \le n \le 10^5, 1 \le b$ 且 $2b \le n$)。每个测试用例的第二行包含 $n$ 个整数：排列 $p$。$1$ 到 $n$ 中的每个整数在该行中恰好出现一次。 输入中所有 $n$ 的总和不超过 $10^5$。

输出格式

输出排列 $p$ 在所有可以通过上述修改得到的排列按字典序排列后的列表中的编号（从 $1$ 开始计数），结果对 $120\,586\,241$ 取模。

样例

输入 1

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

输出 1

31
3