Takahashi is about to assemble a character figure, consisting of N parts called Part 1, Part 2, ..., Part N and N-1 connecting components. Parts are distinguishable, but connecting components are not.
Part i has d_i holes, called Hole 1, Hole 2, ..., Hole d_i, into which a connecting component can be inserted. These holes in the parts are distinguishable.
Each connecting component will be inserted into two holes in different parts, connecting these two parts. It is impossible to insert multiple connecting components into a hole.
The character figure is said to be complete when it has the following properties:
 - All of the N-1 components are used to connect parts.
 - Consider a graph with N vertices corresponding to the parts and N-1 undirected edges corresponding to the pairs of vertices connected by a connecting component. Then, this graph is connected.
Two ways A and B to make the figure complete are considered the same when the following is satisfied: for every pair of holes, A uses a connecting component to connect these holes if and only if B uses one to connect them.
Find the number of ways to make the figure complete. Since the answer can be enormous, find the count modulo 998244353.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 2 \times 10^5
 - 1 \leq d_i < 998244353

-----Input-----
Input is given from Standard Input in the following format:
N
d_1 d_2 \cdots d_N

-----Output-----
Print the answer.

-----Sample Input-----
3
1 1 3

-----Sample Output-----
6

One way to make the figure complete is to connect Hole 1 in Part 1 and Hole 3 in Part 3 and then connect Hole 1 in Part 2 and Hole 1 in Part 3.

Difficulty: VERY_HARD

Starter code:

Solutions:
(P, a, I) = (998244353, 1, input)
n = int(I())
d = list(map(int, I().split()))
s = sum(d) % P
for i in d:
	a = a * i % P
for i in range(n, 2 * n - 2):
	a = a * (s - i) % P
print(a)


import sys
from sys import stdin
N = int(stdin.readline())
d = list(map(int, stdin.readline().split()))
S = sum(d)
if sum(d) < 2 * (N - 1):
	print(0)
	return
mod = 998244353
ans = 1
for i in d:
	ans *= i
	ans %= mod
for i in range(S - N, S - 2 * N + 3 - 1, -1):
	ans *= i
	ans %= mod
print(ans)


import math
mod = 998244353
N = int(input())
L = list(map(int, input().split()))
if sum(L) < 2 * (N - 1):
	print(0)
	return
ans = 1
for i in L:
	ans *= i
	ans %= mod
c = sum(L)
for i in range(N - 2):
	ans *= c - N - i
	ans %= mod
ans %= mod
print(ans)


(n, *d) = map(int, open(0).read().split())
(a, m, s) = (1, 998244353, sum(d))
d.extend(range(s - 2 * n + 3, s - n + 1))
for i in d:
	a = a * i % m
print(a)


mod = 998244353
n = int(input())
d = list(map(int, input().split()))
s = sum(d) % mod
ans = 1
for i in d:
	ans *= i
	ans %= mod
for i in range(n, 2 * n - 2):
	ans *= s - i
	ans %= mod
print(ans)


m = 998244353
(n, *d) = map(int, open(0).read().split())
a = s = 1
for v in d:
	a = a * v % m
	s += v - 1
while n - 2:
	a = a * (s + 2 - n) % m
	n -= 1
print(a)


I = input
n = int(I())
(*d,) = map(int, I().split())
a = 1
m = 998244353
s = sum(d)
d.extend(range(s - 2 * n + 3, s - n + 1))
for i in d:
	a *= i
	a %= m
print(a)


MOD = 998244353
N = int(input())
ds = list(map(int, input().split()))
sigma_d = 0
pi_d = 1
for d in ds:
	sigma_d += d
	sigma_d %= MOD
	pi_d *= d
	pi_d %= MOD
perm = 1
for i in range(N - 2):
	perm *= sigma_d - N - i
	perm %= MOD
print(perm * pi_d % MOD)


(n, *d) = map(int, open(0).read().split())
(s, r, m) = (sum(d), 1, 998244353)
for v in d:
	r = r * v % m
for i in range(n - 2):
	r = r * (s - n - i) % m
print(r)


import sys
readline = sys.stdin.readline
read = sys.stdin.read
n = int(readline())
(*d,) = map(int, readline().split())
MOD = 998244353
ans = 1
v = sum(d) - n
for i in range(n - 2):
	ans *= v
	ans %= MOD
	v -= 1
for i in d:
	ans *= i
	ans %= MOD
print(ans)


N = int(input())
D = list(map(int, input().split()))
mod = 998244353
ANS = 1
S = 0
for d in D:
	ANS = ANS * d % mod
	S += d
for i in range(N - 2):
	ANS = ANS * (S - N - i) % mod
print(ANS)


m = 998244353
(n, *d) = map(int, open((y := 0)).read().split())
a = 1
for v in d:
	a = a * v % m
	y += v - 1
for i in range(n - 2):
	a = a * (y - i) % m
print(a)


N = int(input())
D = list(map(int, input().strip().split()))
MOD = 998244353
ans = 1
for d in D:
	ans *= d
	ans %= MOD
dsum = sum(D) - N
for i in range(N - 2):
	ans *= dsum - i
	ans %= MOD
print(ans)


import numpy as np
import sys
from sys import stdin

def main():
	s = sum(d)
	ans = 1
	for i in range(n):
		ans = ans * d[i] % m
	for i in range(n, 2 * n - 2):
		ans = ans * (s - i) % m
	return ans
input = sys.stdin.readline
n = int(input())
d = list(map(int, input().split()))
m = 998244353
print(main())


def main(n, d):
	mod = 998244353

	def cmb(n, r, mod):
		if r < 0 or r > n:
			return 0
		r = min(r, n - r)
		return g1[n] * g2[r] * g2[n - r] % mod
	g1 = [1, 1]
	g2 = [1, 1]
	inverse = [0, 1]
	for i in range(2, n + 1):
		g1.append(g1[-1] * i % mod)
		inverse.append(-inverse[mod % i] * (mod // i) % mod)
		g2.append(g2[-1] * inverse[-1] % mod)
	ret = 1
	zan = 0
	for x in d:
		ret *= x
		ret %= mod
		zan += x - 1
		zan %= mod
	zan %= mod
	for i in range(n - 2):
		ret *= zan
		ret %= mod
		zan -= 1
	return ret
	for i in range(2 * n - 1):
		ret *= i + 1
		ret %= mod
	return ret
n = int(input())
d = list(map(int, input().split()))
print(main(n, d))


N = int(input())
d = [int(i) for i in input().split()]
ans = 1
mod = 998244353
for i in range(N):
	ans = ans * d[i] % mod
S = sum(d) % mod
for i in range(N - 2):
	ans *= S - N - i
	ans %= mod
print(ans)


MOD = 998244353
n = int(input())
dlst = list(map(int, input().split()))
ans = 1
total = sum(dlst)
if total < 2 * (n - 1):
	print(0)
	return
for d in dlst:
	ans *= d
	ans %= MOD
total -= n
for _ in range(n - 2):
	ans *= total
	ans %= MOD
	total -= 1
print(ans)


def solve(n, ddd):
	s = sum(ddd)
	if s < 2 * (n - 1):
		return 0
	ans = 1
	MOD = 998244353
	for d in ddd:
		ans = ans * d % MOD
	male = n - 1
	female = s - n
	div = 1
	for i in range(n - 2):
		ans = ans * (male - i) * (female - i) % MOD
		div = div * (i + 1) % MOD
	div = div * (n - 1) % MOD
	ans = ans * pow(div, MOD - 2, MOD) % MOD
	return ans
n = int(input())
ddd = list(map(int, input().split()))
print(solve(n, ddd))


mod = 998244353
(N, *D) = map(int, open(0).read().split())
ans = 1
for d in D:
	ans = ans * d % mod
S = sum(D)
for i in range(N - 2):
	ans = ans * (S - N - i) % mod
print(ans)


import sys
input = sys.stdin.readline
ppp = 998244353
n = int(input())
d = list(map(int, input().split()))
prod = 1
sum = 0
for i in range(n):
	prod *= d[i]
	prod %= ppp
	sum += d[i]
	sum %= ppp
sum -= n
answer = prod
for i in range(n - 2):
	prod *= sum - i
	prod %= ppp
print(prod)