T组n,m,k数据,均为正整数，且1<=n<=m<=$10^{5}$,1<=T,k<=$10^{5}$ 计算下列式子(答案对 109+7 取模)：

$m^{nk}$ - $(m^{n}-\sum_n^m{{n-1 \choose i-1}})^{k}$

本人代码(当n,m,k较大时结果为负数！）

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
long long a[100010];
long long Mod=1e9 + 7;
long long fac[100010];
long long inv[100010];

long long quick(long long a,long long b)
{
	long long ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=(ans*a)%Mod;
		}
		a=a*a%Mod;
		b>>=1;
	}
	return ans;
}
void getfac()
{
	fac[0]=inv[0]=1;
	for(int i=1;i<=100000;i++)
	{
		fac[i]=fac[i-1]*i%Mod;
		inv[i]=quick(fac[i],Mod-2); 
	}
}
long long getans(long long n,long long m)
{
	return fac[n]*inv[n-m]%Mod*inv[m]%Mod;
}
long long jishuan(long long n,long long m,long long k)
{
	long long t1=quick(m,n);
	long long t2=quick(t1,k);
	long long sum=getans(m,m-n);
	long long t3=quick((t1-sum)%Mod,k);
//	cout<<t2<<" "<<t3<<endl; 
	return t2-t3;
}
long long  read(){
	long long  ans=0;
	char last=' ',ch=getchar();
	while(ch<'0' || ch>'9')last=ch,ch=getchar();
	while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
	if(last=='-')ans=-ans;
	return ans;
}
int main()
{
//	freopen("boat.in","r",stdin);
//	freopen("biao.out","w",stdout);
	int t;
	getfac();
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		long long t1,t2,t3;
		t1=read();
		t2=read();
		t3=read();
		a[i]=jishuan(t1,t2,t3);
	}
	for(int i=1;i<=t;i++)
		printf("%d\n",a[i]);
	return 0;
 }