高阶等差数列解法 TLE 求条

#include <iostream>
#include <cstring>
#include <cmath>
#define big long long
using namespace std;
constexpr big mod = 998244353;
big T,k,n,m;
big ans;
big val[2000006],jc[2000006];
big cal[2000006]={1}; // 预处理 n 阶等差数列求和公式
big inv[2000006];
big ksm(big x,big k)
{
    big rt = 1, tmp = x;
    while(k)
    {
        if(k&1) rt = rt*tmp%mod;
        k >>= 1;
        tmp = tmp*tmp%mod;
    }
    return rt;
}
void init()
{
    big N = m;
    cal[1] = N;
    cal[2] = N*(N+1)%mod*ksm(jc[2],mod-2)%mod;
    for(big i = 2;i <= n;i++) cal[i+1] = cal[i]*jc[i]%mod*ksm(jc[i+1],mod-2)%mod*(N+i)%mod;
}
int main()
{
    jc[0] = 1;
    for(big i = 1;i <= 2000000;i++) jc[i] = (jc[i-1]*i)%mod;
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld %lld %lld",&n,&m,&k);
        init();
        ans = 0; big base = k;
        for(big i = n-1;i >= 0;i--)
        {
            ans = (ans+cal[i]*k%mod)%mod;
            k = k*base%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}