读入T组n,m,k数据,均为正整数，且1<=n<=m<=$10^{5}$,1<=T,k<=$10^{5}$,计算下列式子：

---

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

---

代码（TLE）

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
long long inf=1000000007;
long long a[100001];

long long c(long long n,long long m)
{
	if(m==0 || m==n)	return 1;
	return c(n-1,m)+c(n-1,m-1);
}
long long mi(long long x,long long p)
{
	long long m,result=1,o,i;
	m=inf;
	o=p;
	i=x;
	while(p)
	{
		if(p%2==1)
		{
			result=result*x%m;
		}
		p/=2;
		x=x*x%m;
	}
	return result%m;
}
long long jishuan(long long n,long long m,long long k)
{
	long long t1=mi(m,n);
	long long t2=mi(t1,k);
	long long sum=0;
	for(long long i=n;i<=m;i++)
	{
		sum+=c(i-1,n-1)%inf;
	}
	long long t3=mi(t1-sum,k);
	return (t2-t3)%inf;
}
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()
{
	int t;
	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;
 } 

本人用组合递推式+快速幂计算，结果仍然TLE(要求time<=1000ms)>。请问还能继续再优化吗？感觉组合数求和式能化简，但数学能力不够。。。