Nasser's Prime Slices

Input

Each test contains multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ $(1 \leq n \leq 2 \cdot 1 0^{5}, 1 \leq k \leq n)$ (1 \le n \le 2 \cdot 10^5, 1 \le k \le n) — the length of the array and the required number of primes per subarray.

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(1 \leq a_{i} \leq 1 0^{7})$ (1 \le a_i \le 10^7) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Output

For each test case, print a single integer — the number of ways to slice the array satisfying the condition, modulo $1 0^{9} + 7$ 10^9+7.

Examples

Example 1

Loading

Note

In the first test case, $n = 6$ n = 6, $k = 2$ k = 2, and $a = [2, 3, 5, 7, 11, 13]$ a = [2, 3, 5, 7, 11, 13]. All elements are prime, so the only valid slicing is $[2, 3] ∣ [5, 7] ∣ [11, 13]$ [2, 3] \mid [5, 7] \mid [11, 13], giving 1 way.

In the fourth test case, $n = 6$ n = 6, $k = 2$ k = 2, and $a = [2, 2, 1, 1, 2, 2]$ a = [2, 2, 1, 1, 2, 2].

$[2, 2] ∣ [1, 1, 2, 2]$ [2, 2] \mid [1, 1, 2, 2]
$[2, 2, 1] ∣ [1, 2, 2]$ [2, 2, 1] \mid [1, 2, 2]
$[2, 2, 1, 1] ∣ [2, 2]$ [2, 2, 1, 1] \mid [2, 2]

This gives 3 ways.

Scoring

Subtask $1$ ( $250$ points) : No additional constraints.