$$F_i(x)=\sum_{n\,is\,odd}^{\infty}p_i^{n}\frac{x^{n}}{n!}$$

$$F_i(x)=\sum_{n\,is\,even}^{\infty}p_i^{n}\frac{x^{n}}{n!}$$

$$e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!}=1+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots+\frac{x^n}{n!}+\cdots\\ e^{-x}=\sum_{n=0}^{\infty}(-1)^{n}\frac{x^n}{n!}=1-\frac{x^1}{1!}+\frac{x^2}{2!}-\frac{x^3}{3!}+\cdots+(-1)^n\frac{x^n}{n!}+\cdots\\$$

$$\sum_{n\,is\,odd}^{\infty}\frac{x^n}{n!}=\frac{x^1}{1!}+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots+[n\text{ is odd}]\frac{x^n}{n!}+\cdots=\frac{e^x-e^{-x}}{2}\\ \sum_{n\,is\,even}^{\infty}\frac{x^n}{n!}=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}+[n\text{ is even}]\frac{x^n}{n!}+\cdots=\frac{e^x+e^{-x}}{2}\\$$

$$F_i(x)= \begin{cases} \frac{e^{p_ix}-e^{-p_ix}}{2}\quad\text{if }i\text{ is odd}\\ \frac{e^{p_ix}+e^{-p_ix}}{2}\quad\text{if }i\text{ is even}\\ \end{cases}$$

$$F_i(x)=\frac{e^{p_ix}+(-1)^{s_i}e^{-p_ix}}{2}$$

\begin{aligned} F(x)&=\prod_{i=1}^{n}F_i(x)\\ &=\prod_{i=1}^{n}\frac{e^{p_ix}+(-1)^{s_i}e^{-p_ix}}{2}\\ \end{aligned}

$$G(x)=\prod_{i=1}^{n}\frac{e^{p_ix}+e^{-p_ix}}{2}\\$$

$$ans=\sum_{i=0}^{\infty}i\cdot ans_i$$

\begin{aligned} C'(1)=\left(\frac{F(1)}{G(1)}\right)’ \end{aligned}

$$\left(\frac{f(x)}{g(x)}\right)’=\frac{f'(x)g(x)-g'(x)f(x)}{[g(x)]^2}$$

$$f'(x)=g'(x)h(x)+g(x)h'(x)\\$$

\begin{aligned} h'(x)&=\frac{f'(x)-g'(x)h(x)}{g(x)}\\ &=\frac{f'(x)-g'(x)\frac{f(x)}{g(x)}}{g(x)}\\ &=\frac{f'(x)g(x)-g'(x)f(x)}{[g(x)]^2}\\ \end{aligned}

$$\frac{F'(1)G(1)-G'(1)F(1)}{[G(1)]^2}$$

\begin{aligned} F(x)&=\prod_{i=1}^{n}\frac{e^{p_ix}+(-1)^{s_i}e^{-p_ix}}{2}\\ G(x)&=\prod_{i=1}^{n}\frac{e^{p_ix}+e^{-p_ix}}{2}\\ \end{aligned}

\begin{aligned} F(1)&=\prod_{i=1}^{n}\frac{e^{p_i}+(-1)^{s_i}e^{-p_i}}{2}\\ G(1)&=\prod_{i=1}^{n}\frac{e^{p_i}+e^{-p_i}}{2}\\ \end{aligned}

$$\sum_{i=-\infty}^{\infty}a_ie^{ix}$$

$$\sum_{i=-\infty}^{\infty}\frac{a_i}{1-ix}$$

\begin{aligned} F(x)&=\sum_{i=-P}^{P}\frac{a_i}{1-\frac{i}{P}x}\\ G(x)&=\sum_{i=-P}^{P}\frac{b_i}{1-\frac{i}{P}x}\\ \frac{F(x)}{G(x)}&=\frac{\sum\limits_{i=-P}^{P}\frac{a_i}{1-\frac{i}{P}x}}{\sum\limits_{i=-P}^{P}\frac{b_i}{1-\frac{i}{P}x}}=\frac{\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)}{\sum\limits_{i=-P}^{P}b_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)}\\ \end{aligned}

$$A(x)=\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)\\ B(x)=\sum\limits_{i=-P}^{P}b_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)\\$$

$$\frac{F'(1)G(1)-G'(1)F(1)}{[G(1)]^2}$$

$$\frac{A'(1)B(1)-A'(1)B(1)}{[B(1)]^2}$$

$$(F(x)G(x))’=F'(x)G(x)+F(x)G'(x)$$

$$\left(\prod_{i=1}^{n}F_i(x)\right)’=\prod_{i=1}^{n}F_i’(x)\left(\prod_{j=1,j\not=i}^{n}F_j(x)\right)$$

\begin{aligned} A’(x)&=\left(\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)\right)’\\ &=\sum\limits_{i=-P}^{P}\left(a_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)\right)’\\ &=\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\left(\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)\right)’\\ &=\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\left(\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)’\left(\prod\limits_{k=-P,k\not=j,k\not=i}^{P}(1-\frac{k}{P}x)\right)\right)\\ &=\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\left(\prod\limits_{j=-P,j\not=i}^{P}(-\frac{j}{P})\left(\prod\limits_{k=-P,k\not=j,k\not=i}^{P}(1-\frac{k}{P}x)\right)\right)\\ \end{aligned}

(公式挂了插个图算了 /kel)

$$S=\prod\limits_{k=-P}^{P-1}(1-\frac{k}{P})$$

$$A'(1)=a_1\left(\prod\limits_{j=-P}^{P-1}(-\frac{j}{P})\frac{S}{1-\frac{j}{P}}\right)-\sum_{i=-P}^{P-1}a_{\frac{i}{P}}\frac{S}{1-\frac{i}{P}}\\$$
$B'(1)$ 的推导一模一样，现在计算 $A'(1)$ 和 $B'(1)$ 的时间复杂度是 $O(P)$ 的了 (可能带个逆元的 $\log$) 。

$$A(1)=a_{1}\prod\limits_{j=-P}^{P-1}(1-\frac{j}{P})\\ B(1)=b_{1}\prod\limits_{j=-P}^{P-1}(1-\frac{j}{P})\\ A'(1)=a_1\left(\prod\limits_{j=-P}^{P-1}(-\frac{j}{P})\frac{S}{1-\frac{j}{P}}\right)-\sum_{i=-P}^{P-1}a_{\frac{i}{P}}\frac{S}{1-\frac{i}{P}}\\ B'(1)=b_1\left(\prod\limits_{j=-P}^{P-1}(-\frac{j}{P})\frac{S}{1-\frac{j}{P}}\right)-\sum_{i=-P}^{P-1}b_{\frac{i}{P}}\frac{S}{1-\frac{i}{P}}\\$$

## Code：

int main() {
#ifndef ONLINE_JUDGE
freopen(".in","r",stdin);
// freopen(".out","w",stdout);
#endif

IN(n);
for(int i=1;i<=n;++i) IN(s[i]);
for(int i=1;i<=n;++i) IN(p[i]),P+=p[i];
invP=modpow(P,mod-2);

memset(tmp,0,sizeof(tmp)),tmp[0][P]=1;
for(int i=1;i<=n;++i) {
int tag=(s[i]&1)?mod-1:1;
for(int j=0;j<=P+P;++j) if(tmp[i-1][j]) {
if(j+p[i]>=0&&j+p[i]<=P+P) pls(tmp[i][j+p[i]],tmp[i-1][j]);
if(j-p[i]>=0&&j-p[i]<=P+P) pls(tmp[i][j-p[i]],mul(tag,tmp[i-1][j]));
}
}
for(int i=0;i<=P+P;++i) a[i]=tmp[n][i];

memset(tmp,0,sizeof(tmp)),tmp[0][P]=1;
for(int i=1;i<=n;++i)
for(int j=0;j<=P+P;++j) if(tmp[i-1][j]) {
if(j+p[i]>=0&&j+p[i]<=P+P) pls(tmp[i][j+p[i]],tmp[i-1][j]);
if(j-p[i]>=0&&j-p[i]<=P+P) pls(tmp[i][j-p[i]],tmp[i-1][j]);
}
for(int i=0;i<=P+P;++i) b[i]=tmp[n][i];

int A=a[P+P],B=b[P+P],T1=1,T2=1,S=1;
for(int i=0;i<P+P;++i) A=mul(A,dec(1,mul(dec(i,P),invP)));
for(int i=0;i<P+P;++i) B=mul(B,dec(1,mul(dec(i,P),invP)));
for(int i=0;i<P+P;++i) S=mul(S,dec(1,mul(dec(i,P),invP)));
for(int i=0;i<P+P;++i) T1=mul(T1,mod-mul(dec(i,P),invP));
for(int i=0;i<P+P;++i) T2=mul(T2,mul(S,modpow(dec(1,mul(dec(i,P),invP)),mod-2)));

int _A=mul(a[P+P],mul(T1,T2)),_B=mul(b[P+P],mul(T1,T2));
for(int i=0;i<P+P;++i) sub(_A,mul(a[i],mul(S,modpow(dec(1,mul(dec(i,P),invP)),mod-2))));
for(int i=0;i<P+P;++i) sub(_B,mul(b[i],mul(S,modpow(dec(1,mul(dec(i,P),invP)),mod-2))));

int ans=mul(dec(mul(_A,B),mul(A,_B)),modpow(mul(B,B),mod-2));
printf("%d\n",ans);
return 0;
}


QAQ