F. Count Subsequences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$ and an integer $$$k$$$. Count the number of different non-empty subsequences of $$$a$$$ with length at most $$$k$$$.

A subsequence is obtained by removing zero or more elements from an array without changing the order of the remaining elements. Two subsequences are different if their lengths differ, or if their values differ at some position. Choosing different indices that give the same sequence of values counts only once.

For example, in the array $$$[1,2,1]$$$, choosing either occurrence of $$$1$$$ gives the same subsequence $$$[1]$$$. The different subsequences of length at most $$$2$$$ are $$$[1]$$$, $$$[2]$$$, $$$[1,2]$$$, $$$[1,1]$$$, and $$$[2,1]$$$, so the answer is $$$5$$$.

Since the answer can be large, print it modulo $$$1000000007$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10000$$$), the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100000$$$, $$$1 \le k \le \min(n,100)$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$100000$$$. There is no additional bound on the sum of $$$k$$$.

Output

For each test case, print the number of different non-empty subsequences of length at most $$$k$$$, modulo $$$1000000007$$$.

Example
Input
4
3 2
1 2 1
3 3
1 1 1
4 2
1 2 3 4
1 1
1
Output
5
3
10
1