#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
const int mod=1e9+7;
int qpow(int x,int t){
if(t==0){return 1;}
if(t%2==1){return qpow(x,t-1)*x%mod;}
int xx=qpow(x,t/2);
return xx*xx%mod;
}
int fac[250005];
int inv[250005];
void precalc(){
fac[0]=1;
for(int i=1;i<=250000;i++){
fac[i]=fac[i-1]*i%mod;
}
inv[250000]=qpow(fac[250000],mod-2);
for(int i=250000-1;i>=0;i--){
inv[i]=inv[i+1]*(i+1)%mod;
}
}
int comb(int x,int y){
if(x<y||y<0){return 0;}
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int n;int K;
signed main(){
}
