#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<assert.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define ull unsigned ll

#define RAND (rand()/(RAND_MAX+1.0))

ll llGCD(ll a,ll b){ll r; while(a){r=b; b=a; a=r%a;} return b;}

/* a^b mod md, a^2 < 2^63, md*a < 2^63 */
ll power_mod(ll a,ll b, ll md){
  ll r;
  if(!b) return 1;
  r = power_mod(a,b/2,md);
  r = (r*r)%md;
  if(b%2) r = (r*a)%md;
  return r;
}

/* ax + by = c = GCD(x,y) */
void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){
  ll a0,a1,a2,b0,b1,b2,r0,r1,r2,q;
  r0=x; r1=y; a0=1; a1=0; b0=0; b1=1;
  while(r1>0){
    q=r0/r1; r2=r0%r1; a2=a0-q*a1; b2=b0-q*b1;
    r0=r1; r1=r2; a0=a1; a1=a2; b0=b1; b1=b2;
  }
  *c=r0; *a=a0; *b=b0;
}

/* n^(-1) mod p */
ll get_inv(ll n, ll p){
  ll a,b,c;
  extended_euclid(n,p,&c,&a,&b);
  if(a<p) a+=p;
  return a%p;
}

int ullNumberOfLeadingZerosTable[256]={8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int ullNumberOfLeadingZeros(ull x){
  int res=56; unsigned xl=x, xh=x>>32;
  if(xh)             res -= 32, xl = xh;
  if(xl&0xffff0000U) res -= 16, xl >>= 16;
  if(xl&0x0000ff00U) res -= 8,  xl >>= 8;
  return res + ullNumberOfLeadingZerosTable[xl];
}

/* (x*y)%m (x,y < m) */
ull ullMultipleMod(ull x, ull y, ull m){
  int k,loop=2;
  ull xlo,xhi,ylo,yhi,rlo,rhi,d1,d2,a,q,r,mask=0xffffffffULL;

  assert(x < m && y < m);
  if(m<=mask) return (x*y)%m;
  
  xlo=(x&mask); xhi=(x>>32);
  ylo=(y&mask); yhi=(y>>32);
  rhi=xhi*yhi; rlo=xlo*ylo;
  a=(rlo>>32)+xhi*ylo;
  rhi+=(a>>32); a&=mask; a+=xlo*yhi; rhi+=(a>>32);
  rlo = (rlo&mask) | ((a&mask)<<32);
  
  k = ullNumberOfLeadingZeros(m);
  rhi = (rhi<<k)|(rlo>>(64-k));
  rlo<<=k; m<<=k;
  
  d1=(m>>32); d2=(m&mask);
  while(loop--){
    r = rhi/d1*d2;
    rhi = ( (rhi%d1 << 32) | (rlo>>32) );
    rlo = ( (rlo&mask) << 32 );
    if(rhi<r) rhi+=m-r; else rhi-=r;
    if(rhi>m) rhi+=m;
  }
  return rhi>>k;
}

/* (x^k)%m */
ull ullPowMod(ull x, ull k, ull m){
  ull res;
  if(k==0) return 1;
  res = ullPowMod(x,k/2,m);
  res = ullMultipleMod(res,res,m);
  if(k%2) res = ullMultipleMod(res,x,m);
  return res;
}


/* prod mod[k] < 2^62*/
/* GCD(mod[i],mod[j]) = 1 */
ll llChineseRemainderTheorem(ll val[], ll mod[], int sz){
  int i, j;
  ll m1, m2, m;
  ll a, b, c, res = 0;

  if(sz==1) return val[0];

  m = 1;
  rep(i,sz) m *= mod[i];

  rep(i,sz){
    m1 = mod[i];
    m2 = m / m1;
    extended_euclid(m1,m2,&c,&a,&b);
    res += ullMultipleMod(((m2*b)%m+m)%m, val[i], m);
    res %= m;
  }

  res %= m;
  if(res < 0) res += m;
  return res;
}

/* mod[sz-2]*mod[sz-1] < 2^62 */
/* GCD(mod[i],mod[j]) = 1, mod[i] < mod[j], i < j */
/* inv[i*sz+j] = mod[j]^(-1) (mod mod[i]), j < i  */
ll llChaineseRemainderTheorem_Garner(ll val[], ll mod[], ll inv[], ll last_mod, int sz, ll *mem){
  int i, j; ll k;
  rep(i,sz) mem[i] = val[i];
  rep(i,sz) rep(j,i){
    k = (mem[i]-mem[j]+mod[i])%mod[i];
    mem[i] = (k*inv[i*sz+j])%mod[i];
  }
  k = 0;
  for(i=sz-1;i>=0;i--){
    k = ullMultipleMod(mod[i]%last_mod,k,last_mod) + mem[i];
    k %= last_mod;
  }
  return k;
}

ll llChineseRemainderTheorem_slow(ll val[], ll mod[], int sz){
  int i, j; ll res;
  
  rep(i,sz) REP(j,i+1,sz) assert( llGCD(mod[i],mod[j])==1 );
  rep(i,sz) assert( 0<=val[i]&&val[i]<mod[i] );
  
  for(res=0;;res++){
    rep(i,sz) if(res%mod[i]!=val[i]) break;
    if(i==sz) break;
  }
  return res;
}

/* n = 2^k */
/* mod % 2^k = 1, mod is a prime */
void fft(int a[], int n, int mod, int primitive_root, int ifft, void *mem){
  int i, j, k, m, mh, x, w, th = 1;
  int *pw = (int*) mem;

  for(k=0;;k++) if((1<<k)>=n) break;
  assert((1<<k)==n);

  primitive_root = power_mod(primitive_root, (mod-1)/(1<<k), mod);
  if(ifft) primitive_root = get_inv(primitive_root, mod);
  pw[0] = 1;
  REP(i,1,n) pw[i] = ((ll)pw[i-1] * primitive_root)%mod;

  for(m=n; m>=2; m/=2){
    mh = m/2;
    rep(i,mh){
      w = ((ll)i*th)%n;
      for(j=i;j<n;j+=m){
        k = j+mh;
        x = ((ll)a[j]-a[k]+mod)%mod;
        a[j] = ((ll)a[j]+a[k])%mod;
        a[k] = ((ll)pw[w]*x)%mod;
      }
    }
    th *= 2;
  }

  i = 0;
  REP(j,1,n-1){
    for(k=n/2; k>(i^=k); k/=2);
    if(j<i) x=a[i], a[i]=a[j], a[j]=x;
  }
}

/* Let k be the minimum integer such that 2^k >= n */
/* size(a), size(b) >= 2^(k+1) */
/* res[k] = a[k]*b[0] + a[k-1]*b[1] + ... + a[0]*b[k] % mod, (a[n] = b[n] = a[n+1] = b[n+1] = ... = 0) */
/* mod is a prime, primitive_root is its primitive root */
void convolution(int a[], int b[], int n, int mod, int primitive_root, int res[], void *mem){
  int i, j, k, inv;
  int *A, *B;

  for(k=0;;k++) if(n <= (1<<k)) break;

  A = (int*) mem; mem = (void*)(A+(1<<(k+1)));
  B = (int*) mem; mem = (void*)(B+(1<<(k+1)));

  rep(i,n) A[i]=a[i], B[i]=b[i];
  REP(i,n,(1<<(k+1))) A[i] = B[i] = 0;

  fft(A, (1<<(k+1)), mod, primitive_root, 0, mem);
  fft(B, (1<<(k+1)), mod, primitive_root, 0, mem);
  rep(i,(1<<(k+1))) res[i] = ((ll)A[i] * B[i]) % mod;
  fft(res, (1<<(k+1)), mod, primitive_root, 1, mem);

  inv = get_inv((1<<(k+1)), mod);
  rep(i,(1<<(k+1))) res[i] = ((ll)res[i] * inv) % mod;
}


int CONV_PRIME_SIZE = 5;
int CONV_PRIME[5] = {2095054849, 2099249153, 2113929217, 2114977793, 2130706433};
int CONV_PRIMITIVE_ROOT[5] = {11, 3, 5, 3, 3};
int CONV_PRIME_INV[25];

void myConvolutionInit(void){
  int i, j;
  rep(i,CONV_PRIME_SIZE) rep(j,CONV_PRIME_SIZE) if(i!=j)
    CONV_PRIME_INV[i*CONV_PRIME_SIZE+j] = get_inv(CONV_PRIME[j], CONV_PRIME[i]);
}

void myComvolution(ll a[], ll b[], int n, ll c[], ll mod, void *mem){
  int i, j, k, sz = 0;
  int **A, **B, **C;
  ll *val, *per_mod, *inv;

  double chk = 1;
  while(chk < (double)mod*mod*(n+1)+1e5) chk *= CONV_PRIME[sz++];

  for(k=0;;k++) if(n <= (1<<k)) break;

  A = (int**)mem; mem = (void*)(A+sz);
  B = (int**)mem; mem = (void*)(B+sz);
  C = (int**)mem; mem = (void*)(C+sz);
  rep(i,sz){
    A[i] = (int*)mem; mem = (void*)(A[i]+(1<<(k+1)));
    B[i] = (int*)mem; mem = (void*)(B[i]+(1<<(k+1)));
    C[i] = (int*)mem; mem = (void*)(C[i]+(1<<(k+1)));
  }
  val     = (ll*)mem; mem = (void*)(val    +sz);
  per_mod = (ll*)mem; mem = (void*)(per_mod+sz);
  inv     = (ll*)mem; mem = (void*)(inv    +sz*sz);

  rep(k,sz) per_mod[k] = CONV_PRIME[k];
  rep(i,sz) rep(j,sz) inv[i*sz+j] = CONV_PRIME_INV[i*CONV_PRIME_SIZE+j];
  
  rep(k,sz){
    rep(i,n) A[k][i] = a[i]%per_mod[k], B[k][i] = b[i]%per_mod[k];
    convolution(A[k],B[k],n,CONV_PRIME[k],CONV_PRIMITIVE_ROOT[k],C[k],mem);
  }

  rep(i,n){ /* rep(i,2*n){ */
    rep(k,sz) val[k] = C[k][i];
    c[i] = llChaineseRemainderTheorem_Garner(val, per_mod, inv, mod, sz, mem);
  }
}


ll small_fact[21000], small_fact_inv[21000];
ll small_inv[21000];

ll smallComb(int a, int b, ll mod){
  ll res;
  if(b<0 || b>a) return 0;
  res = ullMultipleMod(small_fact[a]%mod, small_fact_inv[b]%mod, mod);
  res = ullMultipleMod(res, small_fact_inv[a-b]%mod, mod);
  return res;
}


/* get a such that: P(x) = sum[k=0..d] a[k] * (x!/k!/(x-k)!) */
/* a[k] = sum[j=0..k] (-1)^(k-j) Comb(k,j) P(j) */
void polyValueToCoef(ll P[], int D, ll res[], ll M, void *mem){
  int i;
  static ll b[100000], c[100000];

  rep(i,D+1){
    b[i] = small_fact_inv[i] % M; if(i%2) b[i] = (M - b[i])%M;
    c[i] = ullMultipleMod(P[i] % M, small_fact_inv[i] % M, M);
  }
  myComvolution(b,c,D+1,res,M,mem);
  rep(i,D+1) res[i] = ullMultipleMod(res[i], small_fact[i]%M, M);
}


ll solve1(ll P[], int D, char N[], ll iN, ll Q, ll M, void *mem){
  int i, j, k, len;
  ll pwQ[11];
  ll res = 0;
  static ll Pm[100000], a[100000], b[100000], c[100000], y[100000];
  ll q_inv, sum, mul, tmp;
  
  if(M==1) return 0;

  rep(i,D+1) Pm[i] = P[i] % M;
  polyValueToCoef(Pm, D, a, M, mem);

  q_inv = get_inv(Q-1, M);

  c[0] = (M-q_inv)%M;
  REP(i,1,D+1){
    c[i] = ullMultipleMod(c[i-1], Q%M, M);
    c[i] = ullMultipleMod(c[i], q_inv, M);
    c[i] = (M-c[i])%M;
  }

  /* sum[j=0..d] a[j] * Q^j * (1-Q)^(-j-1) */
  rep(j,D+1){
    res += ullMultipleMod(a[j], c[j], M);
    res %= M;
  }

  /* - Q^n sum[0<=k<=j<=d] a[j]*Comb(n,k)*Q^(j-k)*(1-Q)^(k-j-1) */
  b[0] = 1;
  REP(i,1,D+1){
    b[i] = ullMultipleMod(b[i-1], ((iN-i+1)%M+M)%M, M);
    b[i] = ullMultipleMod(b[i], small_inv[i]%M, M);
  }

  myComvolution(b,c,D+1,y,M,mem);
  sum = 0;

/*  mul = ullPowMod(Q%M, N, M);*/
  mul = 1;
  pwQ[0] = 1;
  REP(i,1,10) pwQ[i] = ullMultipleMod(pwQ[i-1], Q%M, M);
  len = strlen(N);
  rep(i,len) mul = ullMultipleMod(ullPowMod(mul, 10, M), pwQ[N[i]-'0'], M);

  rep(i,D+1){
    sum += ullMultipleMod(a[i], y[i], M);
    sum %= M;
  }
  sum = (M-sum)%M;
  res += ullMultipleMod(sum,mul,M);
  res %= M;

  return res;
}

ll solve2(ll P[], int D, char N[], ll iN, ll Q, ll M, void *mem){
  int i, j, k, a;
  ll res = 0;
  static ll comb_memo[100000], T[100000];
  static ll b[100000], c[100000], t[100000];
  ll rem, add, mul;
  
  if(M==1) return 0;

  /* a is the minimum integer such that (Q-1)^a % M = 0 */
  for(a=0;;a++){
    rem = ullPowMod((Q-1)%M, a, M);
    if(!rem) break;
  }

  rep(i,D+2) comb_memo[i] = smallComb(D+1, i, M);

  REP(i,D+1,D+a){
    P[i] = 0;
    REP(j,1,D+2){
      add = ullMultipleMod(comb_memo[j], P[i-j]%M, M);
      if(j%2==1) P[i] += add;
      else       P[i] -= add;
      P[i] %= M;
    }
    if(P[i] < 0) P[i] += M;
  }

  mul = 1;
  rep(i,D+a){
    T[i] = ullMultipleMod(P[i]%M, mul, M);
    mul = ullMultipleMod(mul, Q%M, M);
  }

  polyValueToCoef(T, D+a-1, t, M, mem);
  mul = iN%M;
  rep(i,D+a){
    res += ullMultipleMod(t[i], mul, M);
    res %= M;
    mul = ullMultipleMod(mul, ((iN-i-1)%M+M)%M, M);
    mul = ullMultipleMod(mul, small_inv[i+2]%M, M);
  }

  return res;
}

int main(){
  int T;
  ll M, Q; int D, sumD = 0;
  static ll P[21000];
  char N[1000000];
  ull iN; /* N mod M */

  int i, j, k, len, lenSum = 0;
  static ll a[100000], b[100000], c[100000];
  ll M1, M2, m;
  ll res, res1, res2;
  void *mem = malloc(40*1000000);

  myConvolutionInit();

  assert( scanf("%d",&T)==1 );
  assert( 1<=T && T<=5000 );
  while(T--){
    assert( scanf("%lld%lld%s%d\n",&M,&Q,N,&D)==4 );
    assert( 1LL<M && M<=1000000000000000000LL );
    assert( 0LL<=Q && Q<M );
    assert( 0<=D && D<20000 );
    sumD += D+1; assert( sumD <= 20000 );
    REP(i,2,D+15) assert( M%i );

    len = strlen(N);
    assert(1<=len && len<=100000);
    rep(i,len) assert('0'<=N[i]&&N[i]<='9');
    assert( N[0]!='0' );
    lenSum += len;
    assert(lenSum <= 100000);

    iN = 0;
    rep(i,len) iN = (iN * 10 + (N[i]-'0'))%M;

    rep(i,D+1) assert( scanf("%lld", P+i)==1 );
    rep(i,D+1) assert( 0LL<=P[i] && P[i]<M );

    if(M==0){ puts("0"); continue; }
    if(Q==0){ printf("%lld\n",P[0]); continue; }

    REP(i,1,D+15) small_inv[i] = get_inv(i, M);
    small_fact[0] = small_fact_inv[0] = 1;
    REP(i,1,D+15) small_fact[i] = ullMultipleMod(small_fact[i-1], i%M, M);
    REP(i,1,D+15) small_fact_inv[i] = ullMultipleMod(small_fact_inv[i-1], small_inv[i], M);

    /* GCD(M1,Q-1)=1 */
    M1 = M;
    for(;;){
      m = llGCD(M1, Q-1);
      if(m==1) break;
      M1 /= m;
    }
    M2 = M/M1;

    res1 = solve1(P, D, N, iN, Q, M1, mem);
    res2 = solve2(P, D, N, iN, Q, M2, mem);
    {
      ll val[2] = {res1, res2};
      ll mod[2] = {M1, M2};
      res = llChineseRemainderTheorem(val, mod, 2);
    }
    printf("%lld\n",res);
  }

  return 0;
}