409878: GYM103821 J Nour's Balls

Nour has just arrived at MIT. He is now standing in front of their gates fully ready to get inside. Unfortunately, there is one more task that the guards asked him to solve to let him get inside.

The guards gave Nour the magical box, which contains $$$N$$$ balls such that the $$$i_{th}$$$ ball has color $$$C_i$$$. Then, they put $$$K$$$ empty boxes in front of Nour and asked him the following question: How many ways there are to partition all $$$N$$$ balls into all $$$K$$$ boxes, such that:

• None of the $$$K$$$ empty boxes is left empty.

• Balls inside each box are considered as multi-set of their colors. i.e a box of colors $$$\{1, 2, 2, 3\}$$$ and a box of colors $$$\{1, 2, 3, 2\}$$$ are considered the same box, while $$$\{1, 2, 2, 3\}$$$ and $$$\{1, 2, 3, 3\}$$$ are two different boxes.

• Boxes within each other are ordered. For example, if the set of colors in the magical box is $$${1, 2, 2, 3}$$$ and $$$K = 2$$$, then [$$$\{1, 2\}$$$, $$$\{2, 3\}$$$] and [$$$\{2, 3\}$$$, $$$\{1, 2\}$$$] are two different ways of partitioning.

In conclusion, two ways are considered different if they differ by at least one i-th box. For example, if colors of balls in the magical box are $$${1, 2, 2}$$$ and $$$K = 2$$$, then there are $$$4$$$ ways: [$$$\{1\}$$$, $$$\{2, 2\}$$$], [$$$\{2, 2\}$$$, $$$\{1\}$$$], [$$$\{1, 2\}$$$, $$$\{2\}$$$], [$$$\{2\}$$$, $$$\{1, 2\}$$$].

This problem is very hard for Nour, can you help him so that he does not get rejected from MIT? If you can, find the answer and print it modulo $$$1\,000\,000\,007$$$.

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$. Description of the test cases follows.

The first line of each test case contains two integers $$$N$$$ and $$$K$$$, $$$(1 \le N \le 10^3)$$$, $$$(1 \le K \le N)$$$ - the number of balls in the magical box and the number of empty boxes.

The second line of each test case contains $$$N$$$ elements of the array $$$C$$$ describing the color of each ball in the magical box $$$(1 \le C_i \le N)$$$.

It's guaranteed that the sum of $$$N\times K$$$ over all test cases does not exceed $$$10^6$$$

For each test case, print a single line containing the described answer modulo $$$1\,000\,000\,007$$$.

2
6 3
1 2 2 1 4 3
4 4
1 2 3 2

219
12

In the second test case, we have $$$4$$$ balls and $$$4$$$ boxes, so it is equal to the number of permutations with repetition of array $$$[1, 2, 2, 3]$$$, which is $$$\frac{4!}{2!} = 12$$$.