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;
}