gdsub-sol

#include <bits/stdc++.h>

#define ll long long
#define mxf 1010
// 'mxf' is the maximum number of distinct primes
const ll mod = 1e9+7;

using namespace std;

int pf[mxf] = {};   //pf array to store frequency of all primes present

int main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);

    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    int n, k;
    cin>>n>>k;  // n->number of primes, k->max length of subsequence permitted
    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        pf[a] += 1; //increasing frequnency of prime 'a'
    }
    vector <ll> f;  //to further filter pf array
    // for example: pf = {1, 0, 0, 3, 4, 0, 7}
    // then f = {1, 3, 4, 7}

    for(int i=0; i<mxf; i++){
        if(pf[i])
            f.push_back(pf[i]);
    }

    int m = f.size();   // m = size of 'f' array
    int dp[m+1][k+1] = {};  // dp table created initialising all elements to 0

    // for(int i=0; i<k+1; i++){
    //     dp[0][i] = 0;
    // }

    for(int i=0; i<m+1; i++){
        dp[i][0] = 1;
    }

    for(int i=1; i<m+1; i++){
        for(int j=1; j<k+1; j++){
            dp[i][j] += ( ( f[i-1]*dp[i-1][j-1] ) % mod + dp[i-1][j] ) % mod;
            dp[i][j] %= mod;
        }
    }

    ll res = 0; // to stroe the final result
    for(int i=0; i<k+1; i++){
        res += dp[m][i] % mod;
        res %= mod;
    }
    cout<<res<<endl;
    return 0;
}