#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,n) for(int i = 0;i<((int)(n));i++) #define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++) #define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--) #define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--) typedef long long ll; typedef pair mp; ll mod = 1e9+7; ll inf = 1e18; struct Factorial{ long long N,mod; vector fact,inv; long long mod_pow(long long x,long long n){ long long res=1; while(n){ if(n&1) (res*=x)%=mod; (x*=x)%=mod; n>>=1; } return res; } long long Inverse(long long n){ return mod_pow(n,mod-2); } Factorial(){} Factorial(long long sn,long long smod){ N=sn; mod=smod; fact.reserve(sn+1); inv.reserve(sn+1); //初期化 fact[0]=1; for(long long i=1;i<=sn;i++){ fact[i]=(fact[i-1]*i) % mod; } inv[sn]=Inverse(fact[sn]); for(long long i=sn;i>0;i--){ inv[i-1]=(inv[i]*i) % mod; } } long long Fact(long long n){ if(n<0)return 0; return fact[n]; } long long Inv(long long n){ if(n<0)return 0; return inv[n]; } long long Combination(long long n,long long r){ if(n>b>>c>>d; b%=mod; c%=mod; Factorial f(1,mod); if(c!=1){ ans=b; ans=(ans*c) % mod; ll t=(1+mod-f.mod_pow(c,d)) % mod; ans=(ans*t) % mod; t=1+mod-c%mod; ans=(ans*f.Inverse(t)) % mod; }else{ ans=b % mod; d%=mod; ans=(ans*d) % mod; } cout<