#include<bits/stdc++.h>
using namespace std;
char op[20];
namespace sub1{//1_998244353
	const int MOD=998244353,MMOD=998244352;
	char s[50];
	int n,len;
	long long zs;
	long long qpow(long long u,long long v){
		long long rep=1;
		while(v>0){
			if(v&1){
				rep=rep*u%MOD;
			}
			u=u*u%MOD;
			v>>=1;
		}
		return rep;
	}
	void solve(){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%s",s);
			len=(int)strlen(s);
			zs=0;
			for(int j=0;j<len;j++){
				zs=zs*10+s[j]-'0';
				zs%=MMOD;
			}
			printf("%lld\n",qpow(19,zs));
		}
	}
}

namespace sub2{//1?
	const int MOD=1145141;
	const int MMOD=MOD-1;
	char s[50];
	int n,len;
	long long zs;
	long long qpow(long long u,long long v){
		long long rep=1;
		while(v>0){
			if(v&1){
				rep=rep*u%MOD;
			}
			u=u*u%MOD;
			v>>=1;
		}
		return rep;
	}
	void solve(){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%s",s);
			len=(int)strlen(s);
			zs=0;
			for(int j=0;j<len;j++){
				zs=zs*10+s[j]-'0';
				zs%=MMOD;
			}
			printf("%lld\n",qpow(19,zs));
		}
	}
}
int main(){
	freopen("haoi2019_software.in","r",stdin);
	freopen("haoi2019_software.out","w",stdout);
	scanf("%s",op);
	if(op[0]=='1'){
		if(op[1]=='_'){//1_998244353
			sub1::solve();
		}
		else if(op[1]=='?'){
			sub2::solve();
		}
	}
}