统计答案时：

for(register int i=1;i<=n;i++)
{
	k_i=(k_i*k)%p;
	ans=(ans+k_i*inv%p*pre[i-1]%p*suf[i+1])%p;
}

（TLE）

for(register int i=n;i>=1;i--)
	ans=(ans*k+inv*pre[i-1]%p*suf[i+1])%p;

（AC，550ms）