310300: CF1811G1. Vlad and the Nice Paths (easy version)

G1. Vlad and the Nice Paths (easy version)time limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an easy version of the problem, it differs from the hard one only by constraints on $n$ and $k$.

Vlad found a row of $n$ tiles and the integer $k$. The tiles are indexed from left to right and the $i$-th tile has the color $c_i$. After a little thought, he decided what to do with it.

You can start from any tile and jump to any number of tiles right, forming the path $p$. Let's call the path $p$ of length $m$ nice if:

• $p$ can be divided into blocks of length exactly $k$, that is, $m$ is divisible by $k$;
• $c_{p_1} = c_{p_2} = \ldots = c_{p_k}$;
• $c_{p_{k+1}} = c_{p_{k+2}} = \ldots = c_{p_{2k}}$;
• $\ldots$
• $c_{p_{m-k+1}} = c_{p_{m-k+2}} = \ldots = c_{p_{m}}$;

Your task is to find the number of nice paths of maximum length. Since this number may be too large, print it modulo $10^9 + 7$.

Input

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

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 100$) — the number of tiles in a row and the length of the block.

The second line of each test case contains $n$ integers $c_1, c_2, c_3, \dots, c_n$ ($1 \le c_i \le n$) — tile colors.

It is guaranteed that the sum of $n^3$ over all test cases does not exceed $5 \cdot 10^6$.

Output

Print $t$ numbers, each of which is the answer to the corresponding test case — the number of nice paths of maximum length modulo $10^9 + 7$.

ExampleInput

5
5 2
1 2 3 4 5
7 2
1 3 1 3 3 1 3
11 4
1 1 1 1 1 1 1 1 1 1 1
5 2
1 1 2 2 2
5 1
1 2 3 4 5

Output

1
4
165
3
1

Note

In the first sample, it is impossible to make a nice path with a length greater than $0$.

In the second sample, we are interested in the following paths:

• $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$
• $2 \rightarrow 4 \rightarrow 5 \rightarrow 7$
• $1 \rightarrow 3 \rightarrow 5 \rightarrow 7$
• $1 \rightarrow 3 \rightarrow 4 \rightarrow 7$

In the third example, any path of length $8$ is nice.

题目大意：
这是一个简化版本的问题，与困难版本的区别仅在于对n和k的限制。

Vlad找到了一行n个瓦片和整数k。瓦片从左到右编号，第i个瓦片的颜色为c_i。他决定对其进行操作。

可以从任一瓦片开始，向右跳过任意数量的瓦片，形成路径p。如果满足以下条件，则称长度为m的路径p为“好路径”：

- p可以划分为长度恰好为k的块，即m能被k整除；
- c_{p_1} = c_{p_2} = … = c_{p_k}；
- c_{p_{k+1}} = c_{p_{k+2}} = … = c_{p_{2k}}；
- …
- c_{p_{m-k+1}} = c_{p_{m-k+2}} = … = c_{p_{m}}；

任务是找到最大长度的好路径的数量。由于这个数字可能太大，所以将其模10^9 + 7后输出。

输入数据格式：
每个测试的第一行包含整数t（1≤t≤10^4）——测试用例的数量。

每个测试用例的第一行包含两个整数n和k（1≤k≤n≤100）——瓦片的行数和块长度。

每个测试用例的第二行包含n个整数c_1, c_2, c_3, …, c_n（1≤c_i≤n）——瓦片的颜色。

保证所有测试用例的n^3之和不超过5 * 10^6。

输出数据格式：
输出t个数字，每个数字对应一个测试用例的答案——最大长度的好路径的数量模10^9 + 7。

示例输入输出（提供了一些测试用例的输入输出对，用于理解题意和验证答案）：

输入：
```
5
5 2
1 2 3 4 5
7 2
1 3 1 3 3 1 3
11 4
1 1 1 1 1 1 1 1 1 1 1
5 2
1 1 2 2 2
5 1
1 2 3 4 5
```
输出：
```
1
4
165
3
1
```

注意：
在第一个样本中，无法制作长度大于0的好路径。
在第二个样本中，我们关注以下路径：
- 1 → 3 → 4 → 5
- 2 → 4 → 5 → 7
- 1 → 3 → 5 → 7
- 1 → 3 → 4 → 7

在第三个示例中，任何长度为8的路径都是好路径。题目大意： 这是一个简化版本的问题，与困难版本的区别仅在于对n和k的限制。 Vlad找到了一行n个瓦片和整数k。瓦片从左到右编号，第i个瓦片的颜色为c_i。他决定对其进行操作。 可以从任一瓦片开始，向右跳过任意数量的瓦片，形成路径p。如果满足以下条件，则称长度为m的路径p为“好路径”： - p可以划分为长度恰好为k的块，即m能被k整除； - c_{p_1} = c_{p_2} = … = c_{p_k}； - c_{p_{k+1}} = c_{p_{k+2}} = … = c_{p_{2k}}； - … - c_{p_{m-k+1}} = c_{p_{m-k+2}} = … = c_{p_{m}}； 任务是找到最大长度的好路径的数量。由于这个数字可能太大，所以将其模10^9 + 7后输出。 输入数据格式： 每个测试的第一行包含整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含两个整数n和k（1≤k≤n≤100）——瓦片的行数和块长度。 每个测试用例的第二行包含n个整数c_1, c_2, c_3, …, c_n（1≤c_i≤n）——瓦片的颜色。 保证所有测试用例的n^3之和不超过5 * 10^6。 输出数据格式： 输出t个数字，每个数字对应一个测试用例的答案——最大长度的好路径的数量模10^9 + 7。 示例输入输出（提供了一些测试用例的输入输出对，用于理解题意和验证答案）： 输入： ``` 5 5 2 1 2 3 4 5 7 2 1 3 1 3 3 1 3 11 4 1 1 1 1 1 1 1 1 1 1 1 5 2 1 1 2 2 2 5 1 1 2 3 4 5 ``` 输出： ``` 1 4 165 3 1 ``` 注意： 在第一个样本中，无法制作长度大于0的好路径。 在第二个样本中，我们关注以下路径： - 1 → 3 → 4 → 5 - 2 → 4 → 5 → 7 - 1 → 3 → 5 → 7 - 1 → 3 → 4 → 7 在第三个示例中，任何长度为8的路径都是好路径。