You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
41 lines
799 B
C++
41 lines
799 B
C++
#include <cstdio>
|
|
using namespace std;
|
|
typedef long long ll;
|
|
const ll mod=1e9+7;
|
|
const int N=1e6+10;
|
|
ll C[N];
|
|
ll qpow(ll a,ll b)
|
|
{
|
|
ll ans=1;
|
|
for(; b; b>>=1)
|
|
{
|
|
if(b&1)
|
|
ans=ans*a%mod;
|
|
a=a*a%mod;
|
|
}
|
|
return ans;
|
|
}
|
|
void calc(ll m,ll n)
|
|
{
|
|
C[0]=1;
|
|
for(int i=1; i<=n; i++)
|
|
C[i]=C[i-1]*(m-i+1)%mod*qpow(i,mod-2)%mod;
|
|
}
|
|
int main()
|
|
{
|
|
int T,t=0,n,m,k;
|
|
scanf("%d",&T);
|
|
while(T--)
|
|
{
|
|
scanf("%d%d%d",&n,&m,&k);
|
|
calc(m,k);
|
|
ll part1=C[k],part2=0;
|
|
calc(k,k);
|
|
ll sign=1;
|
|
for(int i=k; i; i--,sign=-sign)
|
|
part2=(part2+(sign*i*qpow(i-1,n-1))%mod*C[i]%mod+mod)%mod;
|
|
printf("Case #%d: %lld\n",++t,part1*part2%mod);
|
|
}
|
|
return 0;
|
|
}
|