#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define int long long

#define P 1234567891

#define N 200

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int T,k,a,n,d,v[N],f[N];

int ksm(int a,int k)

{

    int s=;

    for (;k;k>>=,a=1ll*a*a%P) if (k&) s=1ll*s*a%P;

    return s;

}

int inv(int a){return ksm(a,P-);}
int calc(int n,int x)

{

    int ans=;

    for (int i=;i<n;i++)

    {

        int u=;for (int j=;j<n;j++) if (i!=j) u=1ll*u*(P+i-j)%P;

        u=1ll*v[i]*inv(u)%P;

        for (int j=;j<n;j++) if (i!=j) u=1ll*u*(P+x-j)%P;

        ans=(ans+u)%P;

    }

    return ans;

}

signed main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3453.in","r",stdin);

    freopen("bzoj3453.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    T=read();

    while (T--)

    {

        k=read(),a=read(),n=read(),d=read();

        memset(v,,sizeof(v));

        for (int i=;i<=k+;i++) v[i]=(v[i-]+ksm(i,k))%P;

        for (int i=;i<=k+;i++) v[i]=(v[i]+v[i-])%P;

        for (int i=;i<=k+;i++) f[i]=calc(k+,(a+1ll*i*d)%P);

        for (int i=;i<=k+;i++) f[i]=(f[i]+f[i-])%P;

        memcpy(v,f,sizeof(v));cout<<calc(k+,n)<<endl;

    }

    return ;

}