# 通らん　なぜ

MOD=998244353
from math import factorial as fact
from collections import defaultdict

def eval(f,x):
  ret=0
  for c in f[::-1]:
    ret=(ret*x+c)%MOD
  return ret

def newton_interpolation(x,y):
  ret=[]
  f=[1]
  for xx,yy in zip(x,y):
    e=eval(f,xx)
    c=eval(ret,xx)
    coef = (yy-c)*pow(e,-1,MOD)%MOD
    ret.append(0)
    for i in range(len(f)): ret[i]=(ret[i]+coef*f[i])%MOD
    for i in range(len(f)-1,0,-1): f[i]=(f[i]*-xx+f[i-1])%MOD
    f[0]=f[0]*-xx%MOD
    f.append(1)
  while ret[-1]==0: ret.pop()
  return ret

S=[
	newton_interpolation(list(range(k+2)),[sum(i**k for i in range(N)) for N in range(k+2)])
	for k in range(23)
]

choose=[[[fact(n)//fact(r)//fact(s)//fact(n-r-s)%MOD for s in range(n-r+1)] for r in range(n+1)] for n in range(23)]

def scary_sum(p,q,N,M,A,B):
  pq=p+q
  ans=0
  memo_main=defaultdict(int)
  memo_main[p,q]=1
  while N>0 and memo_main:
    A1,A=A//M,A%M
    B1,B=B//M,B%M
    memo_sub=defaultdict(int)
    A1pow=[1]
    for i in range(pq):A1pow.append(A1pow[-1]*A1%MOD)
    B1pow=[1]
    for i in range(pq):B1pow.append(B1pow[-1]*B1%MOD)
    for (p,q),coef_main in memo_main.items():
      for r in range(q+1):
        for s in range(q-r+1):
          coef = choose[q][r][s] * A1pow[s] * B1pow[q-r-s]%MOD
          if coef!=0: memo_sub[p+s,r]+=coef*coef_main%MOD
    memo_main=defaultdict(int)
    SpN=[eval(S[p],N) for p in range(pq+1)]
    K=(A*(N-1)+B)//M
    Kpow=[1]
    for i in range(pq):Kpow.append(Kpow[-1]*K%MOD)
    for (p,q),coef_sub in memo_sub.items():
      if q==0:
        ans+=SpN[p]*coef_sub%MOD
        continue
      if K==0: continue
      ans += Kpow[q] * SpN[p] *coef_sub %MOD
      for i in range(q):
        for j in range(p+2):
          coef=choose[q][i][0]*S[p][j]%MOD
          if coef!=0:
            memo_main[i,j]-=coef*coef_sub%MOD
    N,M,A,B=K,A,M,M-B+A-1
  return ans%MOD


T=int(input())
for _ in range(T):
	temp=list(map(int,input().split()))
	temp[2]+=1
	print(scary_sum(*temp)%998244353)