推一下柿子就好了:

,代入得:

可以发现,当 时答案肯定为 ,所以只需要考虑 的情况。那么这个东西也像上面预处理出来就可以 回答询问了,代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 1000010
#define mod 199999

int T,n;
char s[maxn];
int sum[maxn],prod[maxn],inv2=(mod+1)/2;

int main()
{
    for(int i=1;i<=maxn-10;i++)sum[i]=(sum[i-1]+1ll*i*i%mod*(i+1)%mod*inv2%mod)%mod;
    prod[0]=1;for(int i=1;i<=maxn-10;i++)prod[i]=1ll*prod[i-1]*i%mod*sum[i]%mod;
    scanf("%d",&T);while(T--)
    {
        scanf("%s",s+1);int m=strlen(s+1);
        if(m>6){printf("0\n");continue;}
        n=0;for(int i=1;i<=m;i++)n=n*10+s[i]-'0';
        printf("%d\n",prod[n]);
    }
}