CF1811G1.Vlad and the Nice Paths (easy version)

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$.

这是一个该问题的简单版本，它与困难版本的唯一区别在于对 $n$ 和 $k$ 的约束不同。

弗拉德发现了一排 $n$ 块瓷砖以及一个整数 $k$。瓷砖从左到右编号，第 $i$ 块瓷砖的颜色为 $c_i$。稍作思考后，他决定如何处理这排瓷砖。

你可以从任意一块瓷砖出发，并向右跳跃任意数量的瓷砖，从而形成一条路径 $p$。若路径 $p$（长度为 $m$）满足以下条件，则称其为优美的路径（nice path）：

• $p$ 可被划分为若干个长度恰好为 $k$ 的块，即 $m$ 能被 $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}}$；

你的任务是求出最长优美路径的条数。由于该数目可能过大，请输出其对 $10^9 + 7$ 取模的结果。

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$.

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

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 100$）—— 分别表示一行中瓷砖的数量以及块的长度。

每个测试用例的第二行包含 $n$ 个整数 $c_1, c_2, c_3, \dots, c_n$（$1 \le c_i \le n$）—— 表示瓷砖的颜色。

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

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$.

输出 $t$ 个数字，每个数字对应一个测试用例的答案——即最长“好路径”的数量对 $10^9 + 7$ 取模的结果。

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.

在第一个样例中，无法构造长度大于 $0$ 的优美路径。

在第二个样例中，我们关注以下路径：

• $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$

在第三个样例中，任意长度为 $8$ 的路径都是优美路径。