UOJ498 新年的追逐战
猜了一个正确结论，写了个错的模拟图合并，以为结论是假的，然后扔了（
赛后兔D了我一下，我才发现（
赛后想了一下觉得得到结论后不难（
考虑\(G_i\)确定的情况下\(H\)的联通块个数。
首先这个乘法显然具有交换律和结合律。
如果\(G_i\)不联通，H联通块个数一定为\(G_i\)每个联通块和其它\(G_j\)乘起来的连通块个数和。
那么考虑\(G_i\)都是联通块的情况。
如果存在一个\(G_i\)点数为1，那么乘起来没有边，连通块个数是\(\prod G_i\)。
否则联通块个数是\(2^{s}\)，\(s=max(0,\) \(G_i\)中二分图的连通块个数\(-1)\)。（我猜到了这个结论 以为它假了）
大概的证明：
以两个联通图\(G_1,G_2\)为例：
如果\(G_1,G_2\)都是二分图，那么\(G_1\ast G_2\)中每个点一定有黑+黑，黑+白，白+黑，白+白四种情况，用11,10,01,00表示，容易发现11只能和00连边，10只能和01连边，于是就会得到两个二分图。
任意两个在同一张图中的点\((u_1,u_2),(v_1,v_2)\)都满足\(G_1\)中\(u_1,v_1\)联通，\(G_2\)中\(u_2,v_2\)联通，且随意各找一条路径奇偶性都相同。由于不要求简单路径，所以存在长度为x的路径就存在x+2的路径，所以一定存在一条\(u_1\)到\(v_1\)的路径，\(u_2\)到\(v_2\)的路径使得长度相等，所以\((u_1,u_2)\)和\((v_1,v_2)\)联通。
如果\(G_1,G_2\)有一个是二分图，不妨设\(G_1\)是二分图。那么\((u_1,u_2)\)和\((v_1,v_2)\)可能有边仅当\(u_1,v_1\)在\(G_1\)中奇偶性不同，所以还是个二分图，由于\(G_2\)有奇环，所以\(u_2\)到\(v_2\)的路径有奇数长度也有偶数长度，类似得\((u_1,u_2)\)和\((v_1,v_2)\)联通。
如果\(G_1,G_2\)都不是二分图，类似可得\(G_1\ast G_2\)是联通图，不是二分图。
类似可得多个图也满足条件。
考虑计算答案：
枚举每个图中一个联通块计算贡献。
如果联通块大小为\(i\)方案数\(\times\)贡献为\(f_i\)，则\(n\)个点的贡献为\(g_n=\sum_{0\leq i\leq n}f_i\binom{n}{i}\)。
则总贡献为\(\prod g_{a_i}\)
首先联通图的生成函数为\(F=\ln G\)，其中\(G(x)=\sum_{i\geq 0} x^i 2^{\binom{i}{2}}\)为无向图的生成函数。
对于存在一个只有1个点的联通块的情况，考虑容斥 块大小任意的贡献和-块大小不为1的贡献和。不限制块大小的情况下，大小为\(x\)的联通块的贡献为\(x\)，方案数\(\times\) 贡献为\(F_x\cdot x\)。
对于不存在只有1个点的联通块的情况，如果所有连通块中二分图个数\(\gt 0\)，那么贡献为\(\frac{2^{s-1}}=\frac{2^s}{2}\)，其中\(s\)是二分图个数，如果个数\(=0\)，那么贡献为\(1=\frac{2^0}{2}+\frac{2^0}{2}\)。
于是先不考虑二分图个数是否为0，每个联通块如果是二分图贡献为2,否则为1，最后\(/2\)。
再加上二分图个数为0的情况的贡献，每个联通块如果不是二分图贡献为1，否则为0，最后\(/2\)。
考虑计算联通二分图的生成函数\(H(x)\)。
设\(A(x)=\sum A_ix^i\)，\(A_n=\sum_{0\leq i\leq n}2^{i(n-i)}\binom{n}{i}=2^{\binom{n}{2}}\sum_{0\leq i\leq n}2^{-\binom{i}{2}}2^{-\binom{n-i}{2}}\binom{n}{i}\)。
也就是说每个点黑白染色，不允许黑点间，白点间连边，黑点白点间任意连边的方案数。
对于每个联通块分成黑白两部分，黑白可以交换。
所以\(A=e^{2H},H=\frac{\ln A}{2}\)。
联通非二分图生成函数显然是\(F-H\)。
于是做完了。
//省略了长长的多项式板子
int f[266667],g[266667],h[266667],fac[266667],inv[266667],invf[266667];
int C(int a,int b){return fac[a]*invf[b]%p*invf[a-b]%p;}
int gr[266667],igr[266667];
int a[100005],w1[266667],w2[266667],w3[266667];
//w1 连通图个数
//w3 联通二分图个数
int s1[266667],s2[266667],s3[266667],s4[266667];
signed main(){
#ifdef QAQAutoMaton
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
#endif
int n=0,m;
read(m);
for(int i=1;i<=m;++i){
read(a[i]);
chkmax(n,a[i]);
}
fac[0]=fac[1]=::inv[1]=invf[0]=invf[1]=1;
for(int i=2;i<=n;++i){
fac[i]=fac[i-1]*i%p;
::inv[i]=(p-p/i)*::inv[p%i]%p;
invf[i]=::inv[i]*invf[i-1]%p;
}
for(int i=0;i<=n;++i){
gr[i]=fpm(2,i*(i-1)>>1);
igr[i]=fpm((p+1)>>1,i*(i-1)>>1);
f[i]=gr[i]*invf[i]%p;
}
ln(n+1,f,w1);
for(int i=0;i<=n;++i){
w1[i]=w1[i]*fac[i]%p;
f[i]=igr[i]*invf[i]%p;
}
Mul(n,f,n,f,g);
for(int i=0;i<=n;++i)w2[i]=g[i]*gr[i]%p;
ln(n+1,w2,w3);
w3[1]=0;
for(int i=2;i<=n;++i){
w3[i]=w3[i]*fac[i]%p*::inv[2]%p;
}
f[0]=f[1]=0;
for(int i=0;i<=n;++i)
g[i]=gr[i]*invf[i]%p;
for(int i=2;i<=n;++i){
f[i]=(w1[i]+w3[i])*invf[i]%p;
}
Mul(n,f,n,g,h);
for(int i=0;i<=n;++i)s1[i]=h[i]*fac[i]%p;
for(int i=2;i<=n;++i){
f[i]=(w1[i]+p-w3[i])*invf[i]%p;
}
Mul(n,f,n,g,h);
for(int i=0;i<=n;++i)s2[i]=h[i]*fac[i]%p;
for(int i=1;i<=n;++i){
f[i]=w1[i]*i%p*invf[i]%p;
}
Mul(n,f,n,g,h);
for(int i=0;i<=n;++i)s3[i]=h[i]*fac[i]%p;
f[1]=0;
Mul(n,f,n,g,h);
for(int i=0;i<=n;++i)s4[i]=h[i]*fac[i]%p;
int w1=1,w2=1,w3=1,w4=1;
for(int i=1;i<=m;++i){
w1=w1*s1[a[i]]%p;
w2=w2*s2[a[i]]%p;
w3=w3*s3[a[i]]%p;
w4=w4*s4[a[i]]%p;
}
write(((w1+w2)*::inv[2]+(w3+p-w4))%p,'\n');
return 0;
}