google-subsequence-of-sizeK

#include<bits/stdc++.h>
using namespace std;
int hell=1000000007;
int com(int n,int r)
{
    if(r>n)return 0;
    long ans=1;
    r=min(r,n-r);
    for(int i=n;i>=n-r+1;i--)ans=(ans*i);
    for(int i=1;i<=r;i++)ans=(ans/i);
    int fin=ans%hell;
    return ans;
}

int main()
{
    int tt;
    cin>>tt;
    while(tt--)
    {
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        map<char,int> ma;
        for(auto i:s)ma[i]++;
        vector<pair<int,char>> v;
        for(auto i:ma)v.push_back({i.second,i.first});
        sort(v.begin(),v.end());
        int nn=v.size();
        int x=0,y=-1;
        int ans=1;
        for(int i=nn-1;i>=0;i--)
        {
            x++;
            if(x>=k)
            {
                y=v[i].first;
                break;
            }
        }
        for(int i=nn-1;i>=0;i--)
        {
            if(v[i].first==y)break;
            k--;
            ans=(ans*v[i].first)%hell;
        }
        x=0;
        for(int i=nn-1;i>=0;i--)
        {
            if(v[i].first==y)x++;
        }
        ans=(ans*com(x,k))%hell;
        for(int i=0;i<k;i++)ans=(ans*y)%hell;
        cout<<ans<<endl;
    }
}