Balls

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
//#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair <ll, int> pli;
typedef pair <ll,  ll>  pll;
typedef pair <int, int> pii;

const int INF = 1e7;
const ll llINF = 1e18;
const int maxN = 1e3 + 9;
const int maxM = 5e3 + 9;
const int maxK = 1e3 + 9;
const int MOD = 1000000007;
const double pi = acos (-1);

int N, K, freq[maxN];
long long memo[maxN][maxK], nCr[2 * maxN][2 * maxK];

long long dp (int currBall, int openedBoxes) {
    if (openedBoxes > K)
        return 0;

    if (currBall > N)
        return openedBoxes == K;

    if (freq[currBall] == 0)
        return dp (currBall + 1, openedBoxes);

    long long ret = 0;
    for (int cnt = 0; cnt <= freq[currBall] && (cnt + openedBoxes <= K); cnt++) {
        if (cnt == 0 && openedBoxes == 0)
            continue;

        int n = freq[currBall] - cnt;
        int k = cnt + openedBoxes;

        ret += nCr[K - openedBoxes][cnt] * nCr[n + k - 1][n] % MOD
                * dp (currBall + 1, k) % MOD;
    }

    return memo[currBall][openedBoxes] = ret;
}

void solve () {
    cin >> N >> K;

    for (int i = 1; i <= N; i++)
        freq[i] = 0;

    for (int i = 1; i <= N; i++) {
        int x;
        cin >> x;

        freq[x]++;
    }

    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= K; j++)
            memo[i][j] = -1;

    cout << dp (1, 0) << "\n";

    return;
}

int main () {
    int testCases = 1;
    cin >> testCases;

    nCr[0][0] = 1;
    for (int i = 1; i < 2 * maxN; i++) {
        nCr[i][0] = nCr[i][i] = 1;

        for (int j = 1; j < i; j++) {
            nCr[i][j] = (nCr[i - 1][j - 1] + nCr[i - 1][j]) % MOD;
        }
    }

    //ios_base::sync_with_stdio (0);
    //cin.tie (0);

    //setIO ("billboard");
    //preCalc ();
    while (testCases--) {
        //initialize common variv1les


        //go solve
        solve ();
    }

    return 0;
}