#include<cstdio>
#include<algorithm>
#include<cstring>
#define mod 9999991
using namespace std;
int t;
long long n;
int fac[mod+1],inv[mod+1];
void fac_inv(long long siz){
fac[0]=inv[0]=fac[1]=inv[1]=1;
for(int i=2;i<=siz;i++){
fac[i] = 1ll*fac[i-1]*i%mod;
inv[i] = 1ll*inv[mod%i]*(mod-mod/i)%mod; //计算逆元
}
}
int C(int n, int m){
if(n<m) return 0;
return 1ll*fac[n]*inv[fac[m]]%mod*inv[fac[n-m]]%mod;
}
int Lucas(long long n,long long m){
if(m==0 || m==n) return 1;
if(n<m) return 0;
if(n<=mod && m<=mod) return C(n,m);
return 1ll*C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
int main(){
scanf("%d",&t);
fac_inv(mod-1);
while(t--){
scanf("%lld",&n);
printf("%lld\n",(1ll*Lucas(2*n,n)*inv[(n+1)%mod])%mod);
}
}
