题面传送门

首先根据我们刚学插值时学的理论知识，\(f(i)\) 是关于 \(i\) 的 \(k+1\) 次多项式。而 \(g(x)\) 是 \(f(x)\) 的前缀和，根据有限微积分那一套理论，\(g(x)\) 是关于 \(x\) 的 \(k+2\) 次多项式。注意到此题 \(k\) 数据范围不过 \(10^2\) 级别，因此我们可以考虑把 \(g\) 多项式的系数插出来。我们代入 \(k+3\) 个点值 \(1,2,3,\cdots,k+3\)，预处理出 \(\prod\limits_{i=1}^{k+3}(x-i)\)，这样每次相当于多项式除以二项式，可以 \(\Theta(k)\) 地计算除法运算的结果，这样我们可以在 \(\Theta(k^2)\) 的时间内计算出 \(g(x)\) 的系数。不妨设 \(g(x)=\sum\limits_{i=0}^{k+2}b_ix^i\)

下面开始推式子：

\[\begin{aligned}
ans&=\sum\limits_{i=0}^ng(a+id)\\
&=\sum\limits_{i=0}^n\sum\limits_{j=0}^{k+2}b_j(a+id)^j\\
&=\sum\limits_{j=0}^{k+2}b_j\sum\limits_{i=0}^n\sum\limits_{l=0}^ja^l(id)^{j-l}\dbinom{j}{l}\\
&=\sum\limits_{j=0}^{k+2}b_j\sum\limits_{l=0}^ja^ld^{j-l}\dbinom{j}{l}\sum\limits_{i=0}^ni^{j-l}
\end{aligned}
\]

后面一个 \(\sum\) 里的东西可以插值求出。注意本质不同的 \(j-l\) 只有 \(k+3\) 个，因此只用插 \(k+3\) 次值，总复杂度 \(\Theta(k^2)\)

const int MAXN=126;
int k,a,n,d;
int qpow(int x,int e){
    int ret=1;
    for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
    return ret;
}
int fac[MAXN+5],ifac[MAXN+5];
void init_fac(int n){
    for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int binom(int n,int k){return 1ll*fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;}
int sum[MAXN+5],pre[MAXN+5],suf[MAXN+5],b[MAXN+5],s[MAXN+5];
int calc_sum(int n,int k){//\sum\limits_{i=0}^ni^k
    if(!k) return n+1;
    for(int i=1;i<=k+2;i++) sum[i]=(0ll+sum[i-1]+qpow(i,k))%MOD;
    pre[0]=suf[k+3]=1;int res=0;
    for(int i=1;i<=k+2;i++) pre[i]=1ll*pre[i-1]*(n-i+MOD)%MOD;
    for(int i=k+2;i;i--) suf[i]=1ll*suf[i+1]*(n-i+MOD)%MOD;
    for(int i=1;i<=k+2;i++){
        int coef=1ll*pre[i-1]*suf[i+1]%MOD;
        coef=1ll*coef*ifac[k+2-i]%MOD*ifac[i-1]%MOD;
        if((k+2-i)&1) coef=MOD-coef;
        res=(0ll+res+1ll*coef*sum[i])%MOD;
    } return res;
}
int ff[MAXN+5];
void add(int v){
    static int tmp[MAXN+5];memset(tmp,0,sizeof(tmp));
    for(int i=0;i<=k+3;i++) tmp[i]=(0ll+((!i)?0:ff[i-1])-1ll*ff[i]*v%MOD+MOD)%MOD;
    for(int i=0;i<=k+3;i++) ff[i]=tmp[i];
}
void div(int v){
    static int tmp[MAXN+5];
    memset(tmp,0,sizeof(tmp));
    int iv=qpow(MOD-v,MOD-2);
    for(int i=0;i<=k+3;i++){
        tmp[i]=(0ll+ff[i]-((!i)?0:tmp[i-1])+MOD)%MOD;
        tmp[i]=1ll*tmp[i]*iv%MOD;
    }
    for(int i=0;i<=k+3;i++) ff[i]=tmp[i];
//    for(int i=0;i<=k+3;i++) printf("%d%c",ff[i]," \n"[i==k+3]);
}
void calc_b(){
    memset(b,0,sizeof(b));
    for(int i=1;i<=k+3;i++) sum[i]=(0ll+sum[i-1]+qpow(i,k))%MOD;
    for(int i=1;i<=k+3;i++) sum[i]=(0ll+sum[i-1]+sum[i])%MOD;
    memset(ff,0,sizeof(ff));ff[0]=1;
    for(int i=1;i<=k+3;i++) add(i);
//    for(int i=0;i<=k+3;i++) printf("%d%c",ff[i]," \n"[i==k+3]);
    for(int i=1;i<=k+3;i++){
        div(i);int mul=1;
        for(int j=1;j<=k+3;j++) if(i^j) mul=1ll*mul*(i-j+MOD)%MOD;
        mul=1ll*qpow(mul,MOD-2)*sum[i]%MOD;
        for(int j=0;j<=k+2;j++) b[j]=(0ll+b[j]+1ll*ff[j]*mul%MOD)%MOD;
        add(i);
    }
}
void solve(){
    scanf("%d%d%d%d",&k,&a,&n,&d);calc_b();int ans=0;
//    for(int i=0;i<=k+2;i++) printf("%d%c",b[i]," \n"[i==k+2]);
    for(int j=0;j<=k+2;j++) s[j]=calc_sum(n,j);
    for(int j=0;j<=k+2;j++) for(int l=0;l<=j;l++){
        int coef=1ll*b[j]*binom(j,l)%MOD*qpow(a,l)%MOD*qpow(d,j-l)%MOD;
        ans=(0ll+ans+1ll*coef*s[j-l]%MOD)%MOD;
    } printf("%d\n",ans);
}
int main(){
    init_fac(MAXN);
    int qu;scanf("%d",&qu);while(qu--) solve();
    return 0;
}
/*
1
2 5 2 5
6755
*/