1833F - Ira and Flamenco - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define sz(x) (ll)(x.size())
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define rep(i, a, b) for (ll i = a; i < b; i++)
const ll MOD = 1000000007; // 998244353
const ll INF = 1e18;

ll exp(ll k, ll m)
{
    if (m == 0)
        return 1;
    ll half = exp(k, m / 2);
    if (m % 2 == 1)
        return (((half * half) % MOD) * k) % MOD;
    else
        return (half * half) % MOD;
}

ll inv(ll x)
{
    return exp(x, MOD - 2);
}

ll ksm(ll x, int y)
{
    ll r = 1;
    while (y)
    {
        if (y & 1)
            r = (ll)r * x % MOD;
        x = (ll)x * x % MOD;
        y >>= 1;
    }
    return r;
}

ll binexp(ll a, ll b)
{
    if (b == 0)
        return 1ll;
    if (b == 1)
        return a % MOD;
    if (b % 2)
        return (a * binexp(a, b - 1)) % MOD;
    return binexp((a * a) % MOD, b / 2);
}

void solve()
{
    ll n, m;
    cin >> n >> m;

    vector<ll> vec(n);
    for (ll i = 0; i < n; i++)
        cin >> vec[i];

    map<ll, ll> freq;
    for (ll i = 0; i < n; i++)
    {
        if (freq.find(vec[i]) == freq.end())
            freq[vec[i]] = 0;
        freq[vec[i]]++;
    }

    sort(all(vec));
    uniq(vec);

    ll k = vec.size();
    if (m > k)
    {
        cout << 0 << endl;
        return;
    }

    map<ll, ll> prod;
    ll temp = 1;
    for (ll i = 0; i < m; i++)
    {
        temp *= freq[vec[i]];
        temp %= MOD;
    }
    prod[0] = temp;
    for (ll i = m; i < k; i++)
    {
        prod[i - m] %= MOD;
        freq[vec[i]] %= MOD;
        prod[i - m + 1] = prod[i - m] * freq[vec[i]];
        prod[i - m + 1] %= MOD;
        // prod[i - m + 1] /= freq[vec[i - m]];
        // prod[i - m + 1] *= exp(freq[vec[i - m]], MOD - 2);
        prod[i - m + 1] *= binexp(freq[vec[i - m]], MOD - 2);
        prod[i - m + 1] += MOD;
        prod[i - m + 1] %= MOD;
    }

    ll ans = 0;
    for (ll i = 0; i < k - m + 1; i++)
    {
        if ((vec[i + m - 1] - vec[i]) < m)
        {
            ans += prod[i];
            ans %= MOD;
        }
    }

    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}