1475E - Advertising Agency - CodeForces Solution

#include "bits/stdc++.h"
using namespace std;
#define ll long long 
#define endl "\n"
const int N= 1e9+7;
# define M_PI   3.14159265358979323846 
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
template<class T> 
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
 
template<class key, class value, class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
/*/---------------------------IO(Debugging)----------------------/*/
 
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> 
istream& operator >> (istream &is, T_container &v) { 
   for(T &x : v) is >> x; return is;
}
#ifdef __SIZEOF_INT128__
ostream& operator << (ostream &os, __int128 const& value){
    static char buffer[64];
    int index = 0;
    __uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value;
    if (value < 0) 
        os << '-';
    else if (T == 0)
        return os << '0';
    for(; T > 0; ++index){
        buffer[index] = static_cast<char>('0' + (T % 10));
        T /= 10;
    }    
    while(index > 0)
        os << buffer[--index];
    return os;
}
istream& operator >> (istream& is, __int128& T){
    static char buffer[64];
    is >> buffer;
    size_t len = strlen(buffer), index = 0;
    T = 0; int mul = 1;
    if (buffer[index] == '-')
        ++index, mul *= -1;
    for(; index < len; ++index)
        T = T * 10 + static_cast<int>(buffer[index] - '0');
    T *= mul;    
    return is;
}
#endif
 
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) { 
   return os << '(' << p.first << ", " << p.second << ')'; 
}
 
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> 
ostream& operator << (ostream &os, const T_container &v) { 
   os << '{'; string sep; 
   for (const T &x : v) os << sep << x, sep = ", "; 
   return os << '}'; 
}
template<class P, class Q = vector<P>, class R = less<P> > ostream& operator << (ostream& out, priority_queue<P, Q, R> const& M){
    static priority_queue<P, Q, R> U;
    U = M;
    out << "{ ";
    while(!U.empty())
        out << U.top() << " ", U.pop();
    return (out << "}");
}
template<class P> ostream& operator << (ostream& out, queue<P> const& M){
    static queue<P> U;
    U = M;
    out << "{"; string sep;
    while(!U.empty()){
        out << sep << U.front(); sep = ", "; U.pop();
    }
    return (out << "}");
}
 
 
#define TRACE
#ifdef TRACE
    #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cerr << name << " : " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
         int count_open = 0, len = 1;
         for(int k = 1; ; ++k){
            char cur = *(names + k);
            count_open += (cur == '(' ? 1 : (cur == ')' ? -1: 0));
            if (cur == ',' && count_open == 0){
               const char* comma = names + k;
               cerr.write(names, len) << " : " << arg1 << " | ";
               __f(comma + 1, args...);
               return;
            }
            len = (cur == ' ' ? len : k + 1);
         }
    }
#else
    #define trace(...) 1
#endif
 
/*/---------------------------RNG----------------------/*/
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int64_t random_long(long long l = LLONG_MIN,long long r = LLONG_MAX){
    uniform_int_distribution<int64_t> generator(l,r);
    return generator(rng);
}
struct custom_hash { // Credits: https://codeforces.com/blog/entry/62393
    static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
    template<typename L, typename R>
    size_t operator()(pair<L,R> const& Y) const{
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(Y.first * 31ull + Y.second + FIXED_RANDOM);
    }
};
 
const int ca=1e5+1;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
#define f(i,n) for(int i=0;i<n;i++)
#define f1(i,n) for(int i=n-1;i>=0;i--)
#define forr(i,a,b) for(ll i=a;i<b;i++)
#define forr1(i,a,b) for(ll i=a-1;i>=b;i--)
#define No cout<<"No"<<endl; 
#define NO cout<<"NO"<<endl;  
#define Yes cout<<"Yes"<<endl; 
#define YES cout<<"YES"<<endl; 
#define out(x) cout<<x<<endl;
typedef priority_queue< pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> mpq;

// Code begins here....................................................................................................................................

vector<int>factorial(1e3+1);


int pw(int a,int b,int c){
    ll ans=1;
    while(b>0){
        if(b&1){
            ans=(ans%N*1ll*a%c)%c;
        }
        a=(a%c*1ll*a%c)%c;
        b>>=1;
    }
    return ans;
}

ll fac(int a, int b){
ll x=factorial[a]%N;
ll d=(factorial[b]*1ll*factorial[a-b])%N;
ll y=pw(d,N-2,N);
ll ans=(x%N*y)%N;
return ans;
}

void solve(){
int n,k; cin>>n>>k;
vi v(n);
cin>>v;
map<int,int>m;
f(i,n)m[v[i]]++;
vi c;
for(auto it : m)c.pb(it.s);
    int sum=0,ct=-1;
f1(i,sz(c)){
if(sum+c[i]<=k){
    sum+=c[i];
}else{
    ct=i;
    break;
}
}
sum=k-sum;
ll ans=1;
for(int i=sz(c)-1;i>=ct;i--){
    if(i==ct){
     if(sum){
      (ans*=fac(c[i],sum))%=N;
     }
    }
}
out(ans)
}
    
int main(){
    factorial[0]=1;
for(int i=1;i<=1e3;++i){
    factorial[i]=(factorial[i-1]*1ll*i)%N;
}    
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  // freopen("knight.in", "r", stdin);
  // freopen("knight.out", "w", stdout);
 int t; cin>>t;
while(t--)
  solve();
 }