#include<bits/stdc++.h> using namespace std; long long _,n,c[500005],dp[500005]; long long md=998244353; int main(){ scanf("%lld%lld",&_,&_); while(_--){ long long flag1=1,tt=0,flag2=1; scanf("%lld",&n); for(int i=1;i<=n*2-1;i++){ if(i%2==1){ scanf("%lld",&c[i]); } else{ char t; scanf(" %c",&t); if(t=='+'){ c[i]=-1; flag2--; } else{ flag1--,tt=i; c[i]=-2; } } } if(flag2==1){ memset(dp,0,sizeof(dp)); long long sum=c[1]; dp[1]=c[1]; for(int i=3;i<=n*2-1;i+=2){ dp[i]=dp[i-2]*c[i]+c[i]; dp[i]%=md; sum+=dp[i]; sum%=md; } printf("%lld\n",sum); continue; } if(flag1==1){ long long sum=0,q=n; for(int i=1;i<=n*2-1;i+=2){ sum=sum+q*c[i]; q=q+n-i-1; sum=sum%md; } printf("%lld\n",sum%md); continue; } if(flag1==0){ long long sum=0,q=n; for(int i=1;i<=n*2-1;i+=2){ if(i!=tt-1 && i!=tt+1 )sum=sum+q*c[i]; q=q+n-i-1; sum=sum%md; } sum=sum+((n*2-1-tt-1)/2+1)%md*((tt-2)/2+1)%md*c[tt-1]%md*c[tt+1]%md; sum=sum%md; sum=sum+((tt-2)/2+1)*c[tt-1]; sum=sum%md; sum=sum+((n*2-1-tt-1)/2+1)*c[tt+1]; printf("%lld\n",sum%md); continue; } long long sum=0; for(int i=1;i<=n*2-1;i+=2){ long long mc=0,now=0; now=c[i],sum+=now; now=now%md; sum=sum%md; if(c[i+1]==-2)mc=c[i]; mc=mc%md; for(int j=i+2;j<=n*2-1;j+=2){ if(c[j-1]==-1){ now+=c[j]; now=now%md; if(c[j+1]==-2)mc=c[j]; else mc=0; mc=mc%md; } else{ now=now-mc+mc*c[j]; now=now%md; if(c[j+1]==-2)mc*=c[j]; else mc=0; mc=mc%md; } sum+=now; sum=sum%md; } } printf("%lld\n",sum); } }