1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
inline int read()
{
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data*w;
}
const int maxn(100010), Mod(998244353), g(3), Invg(332748118);
int fastpow(int x, int y)
{
int ans = 1;
while(y)
{
if(y & 1) ans = 1ll * ans * x % Mod;
x = 1ll * x * x % Mod, y >>= 1;
}
return ans;
}
typedef std::vector<int> vector;
vector ploy[maxn << 1], *l, *r, R;
template<int opt> void FFT(vector &p, int n)
{
for(RG int i = 1; i < n; i++) if(i < R[i]) std::swap(p[i], p[R[i]]);
for(RG int i = 1; i < n; i <<= 1)
{
int rot = fastpow(opt == 1 ? g : Invg, (Mod - 1) / (i << 1));
for(RG int j = 0; j < n; j += (i << 1))
{
int w = 1;
for(RG int k = 0; k < i; ++k, w = 1ll * w * rot % Mod)
{
int x = p[j + k], y = 1ll * w * p[i + j + k] % Mod;
p[j + k] = (x + y) % Mod, p[i + j + k] = (x - y + Mod) % Mod;
}
}
}
}
void Mul(vector &a, vector &b, vector &c)
{
int newL = a.size() + b.size() - 1, N = 1, P;
for(P = 0; N < newL; N <<= 1, ++P);
a.resize(N); b.resize(N);
c.resize(N); R.resize(N);
for(RG int i = 1; i < N; i++)
R[i] = (R[i >> 1] >> 1) | ((i & 1) << (P - 1));
FFT<1>(a, N); FFT<1>(b, N);
for(RG int i = 0; i < N; i++) c[i] = 1ll * a[i] * b[i] % Mod;
FFT<-1>(c, N); a.clear(); b.clear();
for(RG int i = 0, inv = fastpow(N, Mod - 2); i < N; i++)
c[i] = 1ll * c[i] * inv % Mod;
}
int w[maxn], n;
int main()
{
n = read(); if(n == 1) return puts("1"), 0;
for(RG int i = 1; i <= n; i++)
ploy[i].resize((w[i] = read()) + 1),
ploy[i][0] = 1, ploy[i][w[i]] = Mod - 1;
l = ploy + 2, r = ploy + n;
while(l != r)
{
++r; Mul(*l, *(l + 1), *r);
l += 2;
}
int ans = 0;
for(RG int i = r -> size() - 1; ~i; i--)
ans = (ans + 1ll * *(r -> begin() + i) *
fastpow((i + w[1]) % Mod, Mod - 2) % Mod) % Mod;
printf("%lld\n", 1ll * ans * w[1] % Mod);
return 0;
}
|