CF2242C.Unstable Elements

You are given a sorted array of integers $[a_1, a_2, \dots, a_n]$. We can perform any number of operations of the following type on this array:

• mark the first element of the array, as well as all elements that are not equal to their left neighbors (that is, all elements $i$ such that $a_i \ne a_{i-1}$).
• then either delete all marked elements or duplicate them (that is, replace each marked element with two identical elements).

For example, consider the array $[\mathbf{1}, 1, 1, \mathbf{2}, \mathbf{4}, 4, \mathbf{5}]$ (marked elements are shown in bold). If we delete all marked elements, we get $[1, 1, 4]$, and if we duplicate them, we get $[1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5]$.

The operations cannot be performed if the array becomes empty. After each operation, every element gets unmarked.

We call an array of integers $b$ reachable if it can be obtained from array $a$ by some number of the described operations. Your task is to count the number of reachable arrays of length $k$.

给你一个已排序的整数数组 $[a_1, a_2, \dots, a_n]$。你可以对该数组执行任意多次如下类型的操作：

• 标记数组的第一个元素，以及所有与其左侧相邻元素不相等的元素（即所有满足 $a_i \ne a_{i-1}$ 的下标 $i$ 对应的元素）；
• 然后，要么删除所有被标记的元素，要么复制所有被标记的元素（即把每个被标记的元素替换为两个完全相同的元素）。

例如，考虑数组 $[\mathbf{1}, 1, 1, \mathbf{2}, \mathbf{4}, 4, \mathbf{5}]$（加粗表示被标记的元素）。若删除所有被标记的元素，则得到 $[1, 1, 4]$；若复制所有被标记的元素，则得到 $[1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5]$。

当数组变为空时，无法再执行操作。每次操作结束后，所有元素均取消标记。

若一个整数数组 $b$ 可通过从数组 $a$ 出发、执行若干次上述操作而得到，则称 $b$ 是可达的。你的任务是：计算长度为 $k$ 的可达数组的个数。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of two lines:

• the first line contains two integers $n$ and $k$ ($1 \le n, k \le 3 \cdot 10^5$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 \le a_2 \le \dots \le a_n \le n$). Note that the array is sorted.

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例由两行组成：

• 第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 3 \cdot 10^5$）；
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_1 \le a_2 \le \dots \le a_n \le n$）。注意：该数组已按非递减顺序排序。

输入的额外约束：所有测试用例的 $n$ 值之和不超过 $3 \cdot 10^5$。

For each test case, output one integer — the number of reachable arrays $b$ of length $k$. It can be shown that, under the constraints of the problem, the answer fits into a standard $32$-bit integer type.

对于每个测试用例，输出一个整数——长度为 $k$ 的可达数组 $b$ 的个数。可以证明，在本题的约束条件下，答案可放入标准的 $32$ 位整数类型中。

In the first example, the following sequence of operations can be performed:

• $[\mathbf{1}] \rightarrow [\mathbf{1}, 1] \rightarrow [\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1, 1, 1] \rightarrow [1, 1, 1, 1, 1]$.

In the second example, it is impossible to obtain an array of length $5$.

In the third example, the following sequence of operations can be performed:

• $[\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1] \rightarrow [1]$.

In the fifth example, the arrays $[1, 1, 2, 2, 2, 2]$ and $[2, 2, 2, 2, 2, 2]$ can be obtained:

• $[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [1, 1, 2, 2, 2, 2]$;
• $[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [\mathbf{1}, 1, \mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{1}, \mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2] \rightarrow [\mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2, 2] \rightarrow [2, 2, 2, 2, 2, 2]$.

In the seventh example, the arrays $[1, 1, 1, 3, 3, 3, 3]$ and $[3, 3, 3, 3, 3, 3, 3]$ can be obtained.

在第一个例子中，可以执行以下操作序列：

• $[\mathbf{1}] \rightarrow [\mathbf{1}, 1] \rightarrow [\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1, 1, 1] \rightarrow [1, 1, 1, 1, 1]$。

在第二个例子中，无法得到长度为 $5$ 的数组。

在第三个例子中，可以执行以下操作序列：

• $[\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1] \rightarrow [1]$。

在第五个例子中，可以得到数组 $[1, 1, 2, 2, 2, 2]$ 和 $[2, 2, 2, 2, 2, 2]$：

• $[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [1, 1, 2, 2, 2, 2]$；
• $[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [\mathbf{1}, 1, \mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{1}, \mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2] \rightarrow [\mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2, 2] \rightarrow [2, 2, 2, 2, 2, 2]$。

在第七个例子中，可以得到数组 $[1, 1, 1, 3, 3, 3, 3]$ 和 $[3, 3, 3, 3, 3, 3, 3]$。