For an array A of length N, let F(A) denote the sum of the product of all the subarrays of A. Formally,

F(A) = \sum_{L=1}^N \sum_{R=L}^N  (\prod_{i=L}^R A_{i}\right )

For example, let A = [1, 0, 1], then there are 6 possible subarrays:

Subarray [1, 1] has product = 1
Subarray [1, 2] has product = 0
Subarray [1, 3] has product = 0
Subarray [2, 2] has product = 0
Subarray [2, 3] has product = 0
Subarray [3, 3] has product = 1

So F(A) = 1+1 = 2.
  
Given a binary array A, determine the sum of F(A) over all the N! orderings of A modulo 998244353.

Note that orderings here are defined in terms of indices, not elements; which is why every array of length N has N! orderings. For example, the 3! = 6 orderings of A = [1, 0, 1] are:
[1, 0, 1] corresponding to indices [1, 2, 3]
[1, 1, 0] corresponding to indices [1, 3, 2]
[0, 1, 1] corresponding to indices [2, 1, 3]
[0, 1, 1] corresponding to indices [2, 3, 1]
[1, 1, 0] corresponding to indices [3, 1, 2]
[1, 0, 1] corresponding to indices [3, 2, 1]

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N denoting the le
- The second line contains N space-separated integers denoting the array A.

------ Output Format ------ 

For each test case, output the sum of F(A) over all the N! orderings of A, modulo 998244353.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 1$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
3
1 0 1
1
0
2
1 1
4
1 1 0 1

----- Sample Output 1 ------ 
16
0
6
120

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
MOD = 998244353
cpraid1 = [1] * 100001
cpraid2 = [1] * 100001
cpraid3 = [1] * 100001
for i in range(2, 100001):
	cpraid1[i] = cpraid1[i - 1] * i % MOD
	cpraid2[i] = MOD - MOD // i * cpraid2[MOD % i] % MOD
	cpraid3[i] = cpraid3[i - 1] * cpraid2[i] % MOD

def C(x, y):
	return 0 if x < 0 or y > x else cpraid1[x] * cpraid3[y] * cpraid3[x - y] % MOD
T = int(input())
for i in range(T):
	(N, K) = (int(input()), 0)
	cpraid = list(map(int, input().split()))
	c = cpraid.count(0)
	for i in range(N - c + 1):
		K += i * C(N - i, c) % MOD
	ans = K * (c + 1) * cpraid1[N - c] * cpraid1[c] % MOD
	print(ans)


MOD = 998244353
cpraid1 = [1] * 100001
cpraid2 = [1] * 100001
cpraid3 = [1] * 100001
for i in range(2, 100001):
	cpraid1[i] = cpraid1[i - 1] * i % MOD
	cpraid2[i] = MOD - MOD // i * cpraid2[MOD % i] % MOD
	cpraid3[i] = cpraid3[i - 1] * cpraid2[i] % MOD

def C(x, y):
	return 0 if x < 0 or y > x else cpraid1[x] * cpraid3[y] * cpraid3[x - y] % MOD
for tc in range(int(input())):
	(n, t) = (int(input()), 0)
	cpraid = list(map(int, input().split()))
	c0 = cpraid.count(0)
	for i in range(n - c0 + 1):
		t += i * C(n - i, c0) % MOD
	ans = t * (c0 + 1) * cpraid1[n - c0] * cpraid1[c0] % MOD
	print(ans)


def dwr(x, y):
	if x < 0 or y > x:
		return 0
	return aditya[x] * dora[y] % motu * dora[x - y] % motu
motu = 998244353
dora = [0] * 1000001
bolu = [0] * 1000001
aditya = [0] * 1000001
aditya[0] = bolu[0] = bolu[1] = dora[0] = dora[1] = 1
for i in range(1, 1000001):
	aditya[i] = aditya[i - 1] * i % motu
for i in range(2, 1000001):
	bolu[i] = motu - motu // i * bolu[motu % i] % motu
for i in range(2, 1000001):
	dora[i] = dora[i - 1] * bolu[i] % motu
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	c = c1 = r = 0
	for i in range(n):
		if arr[i] == 0:
			c += 1
		else:
			c1 += 1
	for i in range(c1 + 1):
		r = (r + i * dwr(c1 + c - i, c)) % motu
	print((((r * (c + 1) - dwr(c1 + c - 2, c - 1)) % motu + motu) % motu + dwr(c1 + c - 2, c - 1)) * aditya[c1] % motu * aditya[c] % motu)


MOD = 998244353
a = [1] * 100001
b = [1] * 100001
c = [1] * 100001
for i in range(2, 100001):
	a[i] = a[i - 1] * i % MOD
	b[i] = MOD - MOD // i * b[MOD % i] % MOD
	c[i] = c[i - 1] * b[i] % MOD

def C(x, y):
	return 0 if x < 0 or y > x else a[x] * c[y] * c[x - y] % MOD
for tc in range(int(input())):
	(n, t) = (int(input()), 0)
	A = list(map(int, input().split()))
	C0 = A.count(0)
	for i in range(n - C0 + 1):
		t += i * C(n - i, C0) % MOD
	ans = t * (C0 + 1) * a[n - C0] * a[C0] % MOD
	print(ans)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)
fact = [0] * (10 ** 5 + 10)
inv_fact = [0] * (10 ** 5 + 10)
fact[0] = inv_fact[0] = 1
for i in range(1, 10 ** 5 + 10):
	fact[i] = fact[i - 1] * i % M1
	inv_fact[i] = pow(fact[i], M1 - 2, M1)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		arr = lis()
		k = 0
		for i in range(n):
			if arr[i]:
				k += 1
		if k == 0:
			print(0)
			continue
		ans = fact[k] * fact[n - k + 1] * fact[n + 1] * inv_fact[k - 1] * inv_fact[n - k + 2] % M1
		print(ans)
main()


from itertools import permutations
import math
m = 998244353
k = 100001
f1 = [1] * k
f2 = [1] * k
f3 = [1] * k
for i in range(2, k):
	f1[i] = f1[i - 1] * i % m
for i in range(2, k):
	f2[i] = m - m // i * f2[m % i] % m
for i in range(2, k):
	f3[i] = f3[i - 1] * f2[i] % m
S = lambda x, y: f1[x] * f3[y] * f3[x - y] % m
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c0 = a.count(0)
	c1 = a.count(1)
	c2 = math.factorial(c0) * math.factorial(c1)
	q = 0
	for i in range(c1 + 1):
		if n - i >= 0 or n - i >= c0:
			q += i * S(n - i, c0) % m
	print((c0 + 1) * q * c2 % m)


import numpy as np
MOD = 998244353
MAXN = 10 ** 5 * 2
(f, finv, inv) = ([1] * (MAXN + 10), [1] * (MAXN + 10), [1] * (MAXN + 10))
for i in range(2, MAXN + 1):
	f[i] = f[i - 1] * i % MOD
	inv[i] = -(MOD // i) * inv[MOD % i] % MOD
	finv[i] = finv[i - 1] * inv[i] % MOD

def C(n, k):
	if n < 0 or k < 0 or n < k:
		return 0
	else:
		return f[n] * finv[k] % MOD * finv[n - k] % MOD
for _ in range(int(input())):
	N = int(input())
	A = [*map(int, input().split())]
	(zero, one, ans) = (A.count(0), A.count(1), 0)
	A = np.array(A)
	if zero == 0:
		print(N * (N + 1) * f[one] % MOD * inv[2] % MOD)
		continue
	for i in range(1, one + 1):
		now = (zero + 1) * (i * (i + 1) // 2) % MOD * C(zero + one - i - 1, one - i) % MOD * f[zero] * f[one] % MOD
		ans = (ans + now) % MOD
	print(ans)


import sys
import os
import math
import collections
Mod = 998244353

def dp(A):
	B = [1] * (3 * A)
	for i in range(2, A):
		B[i] = B[i - 1] * i % Mod
		B[i + A] = Mod - int(Mod / i) * B[Mod % i + A] % Mod
		B[i + 2 * A] = B[i - 1 + 2 * A] * B[i + A] % Mod
	return B

def Comeon(x, y):
	return B[x] * B[y + 2 * A] * B[x - y + 2 * A] % Mod
T = int(input())
A = 100001
B = dp(A)
for _ in range(T):
	N = int(input())
	C = list(map(int, input().split()))
	(D, E) = (0, C.count(0))
	for i in range(N - E, -1, -1):
		D += i * Comeon(N - i, E) % Mod
	F = D * (E + 1) * B[N - E] * B[E] % Mod
	print(F)


a = [0] * 1000001
b = [0] * 1000001
d = [0] * 1000001
m = 998244353

def f_1(x, y):
	if x < 0 or y > x:
		return 0
	return a[x] * d[y] % m * d[x - y] % m
a[0] = b[0] = b[1] = d[0] = d[1] = 1
for i in range(1, 1000001):
	a[i] = a[i - 1] * i % m
for i in range(2, 1000001):
	b[i] = m - m // i * b[m % i] % m
for i in range(2, 1000001):
	d[i] = d[i - 1] * b[i] % m
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	c = c1 = r = 0
	for i in range(n):
		if arr[i] == 0:
			c += 1
		else:
			c1 += 1
	for i in range(c1 + 1):
		r = (r + i * f_1(c1 + c - i, c)) % m
	print((((r * (c + 1) - f_1(c1 + c - 2, c - 1)) % m + m) % m + f_1(c1 + c - 2, c - 1)) * a[c1] % m * a[c] % m)


e = 100001
(dp, MOD) = ([1] * (3 * e), 998244353)
for i in range(2, e):
	dp[i] = dp[i - 1] * i % MOD
	dp[i + e] = MOD - MOD // i * dp[MOD % i + e] % MOD
	dp[i + 2 * e] = dp[i - 1 + 2 * e] * dp[i + e] % MOD
C = lambda x, y: dp[x] * dp[y + 2 * e] * dp[x - y + 2 * e] % MOD
for tc in range(int(input())):
	(n, t) = (int(input()), 0)
	a = tuple(map(int, input().split())).count(0)
	for i in range(n - a + 1):
		if not (n - i < 0 or a > n - i):
			t += i * C(n - i, a) % MOD
	print(t * (a + 1) * dp[n - a] * dp[a] % MOD)


M = 998244353
arr1 = [0] * 1000010
arr2 = [0] * 1000010
arr3 = [0] * 1000010
arr1[0] = arr2[0] = arr2[1] = arr3[0] = arr3[1] = 1
for i in range(1, 1000001):
	arr1[i] = arr1[i - 1] * i % M
for i in range(2, 1000001):
	arr2[i] = M - M // i * arr2[M % i] % M
for i in range(2, 1000001):
	arr3[i] = arr3[i - 1] * arr2[i] % M

def func(a, b):
	if a < 0 or b > a:
		return 0
	return arr1[a] * arr3[b] % M * arr3[a - b] % M
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	x = y = z = 0
	for i in range(N):
		if A[i] == 0:
			x += 1
		else:
			y += 1
	for i in range(y + 1):
		z = (z + i * func(y + x - i, x)) % M
	print((((z * (x + 1) - func(y + x - 2, x - 1)) % M + M) % M + func(y + x - 2, x - 1)) * arr1[y] % M * arr1[x] % M)


e = 100001
(d, m) = ([1] * (3 * e), 998244353)
for i in range(2, e):
	d[i] = d[i - 1] * i % m
	d[i + e] = m - m // i * d[m % i + e] % m
	d[i + 2 * e] = d[i - 1 + 2 * e] * d[i + e] % m
C = lambda x, y: d[x] * d[y + 2 * e] * d[x - y + 2 * e] % m
for _ in range(int(input())):
	(n, t) = (int(input()), 0)
	c0 = tuple(map(int, input().split())).count(0)
	for i in range(n - c0 + 1):
		if not (n - i < 0 or c0 > n - i):
			t += i * C(n - i, c0) % m
	print(t * (c0 + 1) * d[n - c0] * d[c0] % m)


global fac, inv, f_inv, mod
fac = [0] * 100001
inv = [0] * 100001
f_inv = [0] * 100001
mod = 998244353

def Func(x, y):
	if x < 0 or y > x:
		return 0
	return fac[x] * f_inv[y] % mod * f_inv[x - y] % mod
fac[0] = inv[0] = inv[1] = f_inv[0] = f_inv[1] = 1
for i in range(1, 100001):
	fac[i] = fac[i - 1] * i % mod
for i in range(2, 100001):
	inv[i] = mod - mod // i * inv[mod % i] % mod
for i in range(2, 100001):
	f_inv[i] = f_inv[i - 1] * inv[i] % mod
t = int(input())
while t:
	count_zero = count_one = a = 0
	n = int(input())
	arr = list(map(int, input().split(' ')))
	for i in range(n):
		if arr[i] == 0:
			count_zero += 1
		else:
			count_one += 1
	for i in range(count_one + 1):
		a = (a + i * Func(count_one + count_zero - i, count_zero)) % mod
	ans = (((a * (count_zero + 1) - Func(count_one + count_zero - 2, count_zero - 1)) % mod + mod) % mod + Func(count_one + count_zero - 2, count_zero - 1)) * fac[count_one] % mod * fac[count_zero] % mod
	print(ans)
	t -= 1


m = 998244353
a_li = [0] * 1000001
b_li = [0] * 1000001
d_li = [0] * 1000001

def sol(x, y):
	if x < 0 or y > x:
		return 0
	return a_li[x] * d_li[y] % m * d_li[x - y] % m
a_li[0] = b_li[0] = b_li[1] = d_li[0] = d_li[1] = 1
for i in range(1, 1000001):
	a_li[i] = a_li[i - 1] * i % m
for j in range(2, 1000001):
	b_li[j] = m - m // j * b_li[m % j] % m
for k in range(2, 1000001):
	d_li[k] = d_li[k - 1] * b_li[k] % m
o = int(input())
for _ in range(o):
	n = int(input())
	li = list(map(int, input().split()))
	u = v = r = 0
	for i in range(n):
		if li[i] == 0:
			u += 1
		else:
			v += 1
	for i in range(v + 1):
		r = (r + i * sol(v + u - i, u)) % m
	print((((r * (u + 1) - sol(u - 2 + v, u - 1)) % m + m) % m + sol(u - 2 + v, u - 1)) * a_li[v] % m * a_li[u] % m)


mod = 998244353
arr1 = [1] * 100001
arr2 = [1] * 100001
arr3 = [1] * 100001
for i in range(2, 100001):
	arr1[i] = arr1[i - 1] * i % mod
	arr2[i] = mod - mod // i * arr2[mod % i] % mod
	arr3[i] = arr3[i - 1] * arr2[i] % mod

def helper(x, y):
	return 0 if x < 0 or y > x else arr1[x] * arr3[y] * arr3[x - y] % mod
for tc in range(int(input())):
	(n, t) = (int(input()), 0)
	inp = list(map(int, input().split()))
	inp0 = inp.count(0)
	for i in range(n - inp0 + 1):
		t += i * helper(n - i, inp0) % mod
	ans = t * (inp0 + 1) * arr1[n - inp0] * arr1[inp0] % mod
	print(ans)


fin = 100001
arr = [1] * (3 * fin)
mod = 998244353
for i in range(2, fin):
	arr[i] = arr[i - 1] * i % mod
	arr[i + fin] = mod - mod // i * arr[mod % i + fin] % mod
	arr[i + 2 * fin] = arr[i - 1 + 2 * fin] * arr[i + fin] % mod
x = lambda a, b: arr[a] * arr[b + 2 * fin] * arr[a - b + 2 * fin] % mod
for _ in range(int(input())):
	n = int(input())
	tupc = list(map(int, input().split())).count(0)
	temp = 0
	for i in range(n - tupc + 1):
		if (n - i < 0 or tupc > n - i) == False:
			val = i * x(n - i, tupc)
			temp += val % mod
	print(temp * (tupc + 1) * arr[n - tupc] * arr[tupc] % mod)


a = [0] * 1000001
b = [0] * 1000001
d = [0] * 1000001
m = 998244353

def fun(x, y):
	if x < 0 and y > x:
		return 0
	return a[x] * d[y] % m * d[x - y] % m
a[0] = 1
b[0] = 1
b[1] = 1
d[0] = 1
d[1] = 1
for i in range(1, 1000001):
	a[i] = a[i - 1] * i % m
for i in range(2, 1000001):
	b[i] = m - m // i * b[m % i] % m
for i in range(2, 1000001):
	d[i] = d[i - 1] * b[i] % m
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	c = 0
	c1 = 0
	r = 0
	for i in range(n):
		if arr[i] == 0:
			c += 1
		else:
			c1 += 1
	for i in range(c1 + 1):
		r = (r + i * fun(c1 + c - i, c)) % m
	print((((r * (c + 1) - fun(c1 + c - 2, c - 1)) % m + m) % m + fun(c1 + c - 2, c - 1)) * a[c1] % m * a[c] % m)


a = 100001
(vv, MOD) = ([1] * (3 * a), 998244353)
for i in range(2, a):
	vv[i] = vv[i - 1] * i % MOD
	vv[i + a] = MOD - MOD // i * vv[MOD % i + a] % MOD
	vv[i + 2 * a] = vv[i - 1 + 2 * a] * vv[i + a] % MOD
C = lambda x, y: vv[x] * vv[y + 2 * a] * vv[x - y + 2 * a] % MOD
for m in range(int(input())):
	(k, j) = (int(input()), 0)
	c = tuple(map(int, input().split())).count(0)
	for i in range(k - c + 1):
		if not (k - i < 0 or c > k - i):
			j += i * C(k - i, c) % MOD
	print(j * (c + 1) * vv[k - c] * vv[c] % MOD)


hhhhhhhhhhhhhhyyyyyyyyyyyuuuuuuuuuu = [0] * 1000001
alkjclankcnkeedkskkcnsknkskskllalaaaknakn = [0] * 1000001
bcbhsbcdhcjdncdncjdncjdcndj = [0] * 1000001
lllalallalllaluucuucukskkskksalkls = 998244353

def bchjbsekadkjaljdlaj(dhbcsjcksbkcaklajdla, wwowowkskwokmksmkxs):
	if dhbcsjcksbkcaklajdla < 0 or wwowowkskwokmksmkxs > dhbcsjcksbkcaklajdla:
		return 0
	return hhhhhhhhhhhhhhyyyyyyyyyyyuuuuuuuuuu[dhbcsjcksbkcaklajdla] * bcbhsbcdhcjdncdncjdncjdcndj[wwowowkskwokmksmkxs] % lllalallalllaluucuucukskkskksalkls * bcbhsbcdhcjdncdncjdncjdcndj[dhbcsjcksbkcaklajdla - wwowowkskwokmksmkxs] % lllalallalllaluucuucukskkskksalkls
hhhhhhhhhhhhhhyyyyyyyyyyyuuuuuuuuuu[0] = alkjclankcnkeedkskkcnsknkskskllalaaaknakn[1] = bcbhsbcdhcjdncdncjdncjdcndj[1] = bcbhsbcdhcjdncdncjdncjdcndj[0] = alkjclankcnkeedkskkcnsknkskskllalaaaknakn[0] = 7 * 7 - 8 * 6
for i in range(1, 1000001):
	hhhhhhhhhhhhhhyyyyyyyyyyyuuuuuuuuuu[i] = hhhhhhhhhhhhhhyyyyyyyyyyyuuuuuuuuuu[i - 1] * i % lllalallalllaluucuucukskkskksalkls
for i in range(2, 1000001):
	alkjclankcnkeedkskkcnsknkskskllalaaaknakn[i] = lllalallalllaluucuucukskkskksalkls - lllalallalllaluucuucukskkskksalkls // i * alkjclankcnkeedkskkcnsknkskskllalaaaknakn[lllalallalllaluucuucukskkskksalkls % i] % lllalallalllaluucuucukskkskksalkls
for i in range(2, 1000001):
	bcbhsbcdhcjdncdncjdncjdcndj[i] = bcbhsbcdhcjdncdncjdncjdcndj[i - 1] * alkjclankcnkeedkskkcnsknkskskllalaaaknakn[i] % lllalallalllaluucuucukskkskksalkls
for dash in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	c = bchdbskjcakndallajlsznjaks = r = 0
	for i in range(n):
		if arr[i] == 0:
			c += 1
		else:
			bchdbskjcakndallajlsznjaks += 1
	for i in range(bchdbskjcakndallajlsznjaks + 1):
		r = (r + i * bchjbsekadkjaljdlaj(bchdbskjcakndallajlsznjaks + c - i, c)) % lllalallalllaluucuucukskkskksalkls
	print((((r * (c + 1) - bchjbsekadkjaljdlaj(bchdbskjcakndallajlsznjaks + c - 2, c - 1)) % lllalallalllaluucuucukskkskksalkls + lllalallalllaluucuucukskkskksalkls) % lllalallalllaluucuucukskkskksalkls + bchjbsekadkjaljdlaj(bchdbskjcakndallajlsznjaks + c - 2, c - 1)) * hhhhhhhhhhhhhhyyyyyyyyyyyuuuuuuuuuu[bchdbskjcakndallajlsznjaks] % lllalallalllaluucuucukskkskksalkls * hhhhhhhhhhhhhhyyyyyyyyyyyuuuuuuuuuu[c] % lllalallalllaluucuucukskkskksalkls)


lllkkksssiiit = [0] * 1000001
lkisyyyhhkka = [0] * 1000001
jsahdaldjlawl = [0] * 1000001
lflsjfsoeoncoe = 998244353

def oscosnosnoeosnfe(nsjknslelnlslnc, iwisojocsnnshbd):
	if nsjknslelnlslnc < 0 or iwisojocsnnshbd > nsjknslelnlslnc:
		return 0
	return lllkkksssiiit[nsjknslelnlslnc] * jsahdaldjlawl[iwisojocsnnshbd] % lflsjfsoeoncoe * jsahdaldjlawl[nsjknslelnlslnc - iwisojocsnnshbd] % lflsjfsoeoncoe
lllkkksssiiit[0] = lkisyyyhhkka[1] = jsahdaldjlawl[1] = jsahdaldjlawl[0] = lkisyyyhhkka[0] = 7 * 7 - 8 * 6
for i in range(1, 1000001):
	lllkkksssiiit[i] = lllkkksssiiit[i - 1] * i % lflsjfsoeoncoe
for i in range(2, 1000001):
	lkisyyyhhkka[i] = lflsjfsoeoncoe - lflsjfsoeoncoe // i * lkisyyyhhkka[lflsjfsoeoncoe % i] % lflsjfsoeoncoe
for i in range(2, 1000001):
	jsahdaldjlawl[i] = jsahdaldjlawl[i - 1] * lkisyyyhhkka[i] % lflsjfsoeoncoe
for dash in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	c = djhskfknskcnkseu = r = 0
	for i in range(n):
		if arr[i] == 0:
			c += 1
		else:
			djhskfknskcnkseu += 1
	for i in range(djhskfknskcnkseu + 1):
		r = (r + i * oscosnosnoeosnfe(djhskfknskcnkseu + c - i, c)) % lflsjfsoeoncoe
	print((((r * (c + 1) - oscosnosnoeosnfe(djhskfknskcnkseu + c - 2, c - 1)) % lflsjfsoeoncoe + lflsjfsoeoncoe) % lflsjfsoeoncoe + oscosnosnoeosnfe(djhskfknskcnkseu + c - 2, c - 1)) * lllkkksssiiit[djhskfknskcnkseu] % lflsjfsoeoncoe * lllkkksssiiit[c] % lflsjfsoeoncoe)


(a, b, d) = ([0] * 1000001, [0] * 1000001, [0] * 1000001)

def foo(temp2, temp3):
	if temp2 < 0 or temp3 > temp2:
		return 0
	return a[temp2] * d[temp3] % 998244353 * d[temp2 - temp3] % 998244353
a[0] = 1
(b[0], b[1]) = (1, 1)
(d[0], d[1]) = (1, 1)
i = 1
while i < 1000001:
	a[i] = a[i - 1] * i % 998244353
	i += 1
i = 2
while i < 1000001:
	b[i] = 998244353 - 998244353 // i * b[998244353 % i] % 998244353
	d[i] = d[i - 1] * b[i] % 998244353
	i += 1
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(c, r) = (0, 0)
	temp1 = 0
	for i in range(n):
		if arr[i] == 0:
			c = c + 1
		else:
			temp1 += 1
	for i in range(temp1 + 1):
		r = (r + i * foo(temp1 + c - i, c)) % 998244353
	print((((r * (c + 1) - foo(temp1 + c - 2, c - 1)) % 998244353 + 998244353) % 998244353 + foo(temp1 + c - 2, c - 1)) * a[temp1] % 998244353 * a[c] % 998244353)


m = 998244353
fir = [0] * (10 ** 6 + 1)
sec = [0] * (10 ** 6 + 1)
thi = [0] * (10 ** 6 + 1)

def func(a, b):
	if a < 0 or b > a:
		return 0
	return fir[a] * thi[b] % m * thi[a - b] % m
fir[0] = sec[0] = sec[1] = thi[0] = thi[1] = 1
for i in range(1, 10 ** 6 + 1):
	fir[i] = fir[i - 1] * i % m
for i in range(2, 10 ** 6 + 1):
	sec[i] = m - m // i * sec[m % i] % m
	thi[i] = thi[i - 1] * sec[i] % m
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	c = c1 = r = 0
	for i in range(n):
		if arr[i] == 0:
			c += 1
		else:
			c1 += 1
	for i in range(c1 + 1):
		r = (r + i * func(c1 + c - i, c)) % m
	print((((r * (c + 1) - func(c1 + c - 2, c - 1)) % m + m) % m + func(c1 + c - 2, c - 1)) * fir[c1] % m * fir[c] % m)


(A, B, D, M) = ([0] * 1000001, [0] * 1000001, [0] * 1000001, 998244353)

def function(X, Y):
	if X < 0 or Y > X:
		return 0
	return A[X] * D[Y] % M * D[X - Y] % M
A[0] = B[0] = B[1] = D[0] = D[1] = 1
for i in range(1, 1000001):
	A[i] = A[i - 1] * i % M
for i in range(2, 1000001):
	B[i] = M - M // i * B[M % i] % M
for i in range(2, 1000001):
	D[i] = D[i - 1] * B[i] % M
for j in range(int(input())):
	N = int(input())
	AR = list(map(int, input().split()))
	C = C1 = R = 0
	for i in range(N):
		if AR[i] == 0:
			C += 1
		else:
			C1 += 1
	for i in range(C1 + 1):
		R = (R + i * function(C1 + C - i, C)) % M
		ANS = (((R * (C + 1) - function(C1 + C - 2, C - 1)) % M + M) % M + function(C1 + C - 2, C - 1)) * A[C1] % M * A[C] % M
	print(ANS)


elo = 100001
(d, M) = ([1] * (3 * elo), 998244353)
for ic in range(2, elo):
	d[ic] = d[ic - 1] * ic % M
	d[ic + elo] = M - M // ic * d[M % ic + elo] % M
	d[ic + 2 * elo] = d[ic - 1 + 2 * elo] * d[ic + elo] % M
C = lambda a, b: d[a] * d[b + 2 * elo] * d[a - b + 2 * elo] % M
for _ in range(int(input())):
	(n, t) = (int(input()), 0)
	c = tuple(map(int, input().split())).count(0)
	for i in range(n - c + 1):
		if not (n - i < 0 or c > n - i):
			t += i * C(n - i, c) % M
	print(t * (c + 1) * d[n - c] * d[c] % M)


fck = 1000001
(fuck, MOD) = ([1] * (3 * fck), 998244353)
for i in range(2, fck):
	fuck[i] = fuck[i - 1] * i % MOD
	fuck[i + fck] = MOD - MOD // i * fuck[MOD % i + fck] % MOD
	fuck[i + 2 * fck] = fuck[i - 1 + 2 * fck] * fuck[i + fck] % MOD
C = lambda x, y: fuck[x] * fuck[y + 2 * fck] * fuck[x - y + 2 * fck] % MOD
for tc in range(int(input())):
	(n, t) = (int(input()), 0)
	number = tuple(map(int, input().split())).count(0)
	for i in range(n - number + 1):
		if not (n - i < 0 or number > n - i):
			t += i * C(n - i, number) % MOD
	print(t * (number + 1) * fuck[n - number] * fuck[number] % MOD)


p = 100001
m = 998244353
d = [1] * (3 * p)
for i in range(2, p):
	d[i] = d[i - 1] * i % m
	d[i + p] = m - m // i * d[m % i + p] % m
	d[i + 2 * p] = d[2 * p + i - 1] * d[i + p] % m
A = lambda x, y: d[x] * d[2 * p + y] * d[2 * p + x - y] % m
test = int(input())
for tc in range(test):
	n = int(input())
	ans = 0
	c = tuple(map(int, input().split())).count(0)
	for i in range(n - c + 1):
		if not (n - i < 0 or c > n - i):
			ans += i * A(n - i, c) % m
	print(ans * (c + 1) * d[n - c] * d[c] % m)


mod = 998244353
x = [0] * 1000001
y = [0] * 1000001
z = [0] * 1000001

def solve(a, b):
	if a < 0 or b > a:
		return 0
	else:
		return x[a] * z[b] % mod * z[a - b] % mod
x[0] = 1
y[0] = 1
y[1] = 1
z[0] = 1
z[1] = 1
for i in range(1, 1000001):
	x[i] = x[i - 1] * i % mod
for j in range(2, 1000001):
	y[j] = mod - mod // j * y[mod % j] % mod
for k in range(2, 1000001):
	z[k] = z[k - 1] * y[k] % mod
for ts in range(int(input())):
	N = int(input())
	ls = list(map(int, input().split()))[:N]
	(a, b, c) = (0, 0, 0)
	for i in range(N):
		if ls[i] == 0:
			a += 1
		else:
			b += 1
	for i in range(b + 1):
		c = (c + i * solve(b + a - i, a)) % mod
	print((((c * (a + 1) - solve(b + a - 2, a - 1)) % mod + mod) % mod + solve(b + a - 2, a - 1)) * x[b] % mod * x[a] % mod)


solve = [1] * (3 * 100001)
mod = 998244353
for i in range(2, 100001):
	solve[i] = solve[i - 1] * i % mod
	solve[i + 100001] = mod - mod // i * solve[mod % i + 100001] % mod
	solve[i + 2 * 100001] = solve[i - 1 + 2 * 100001] * solve[i + 100001] % mod

def ans(x, y):
	return solve[x] * solve[y + 2 * 100001] * solve[x - y + 2 * 100001] % mod
for tc in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	cnt = 0
	for i in range(n):
		if ar[i] == 0:
			cnt += 1
	p = 0
	for i in range(n - cnt + 1):
		if not (n - i < 0 or cnt > n - i):
			p += i * ans(n - i, cnt) % mod
	print(p * (cnt + 1) * solve[n - cnt] * solve[cnt] % mod)


exp = 100001
dp = [1] * (3 * 100001)
mod = 998244353
for i in range(2, exp):
	dp[i] = dp[i - 1] * i % mod
	dp[i + exp] = mod - mod // i * dp[mod % i + exp] % mod
	dp[i + exp * 2] = dp[i - 1 + exp * 2] * dp[i + exp] % mod
temp = lambda j, k: dp[j] * dp[k + exp * 2] * dp[j - k + exp * 2] % mod
for test in range(int(input())):
	n = int(input())
	ty = 0
	id = tuple(map(int, input().split())).count(0)
	for it in range(n - id + 1):
		if not (n - it < 0 or id > n - it):
			ty = ty + it * temp(n - it, id) % mod
	print(ty * (id + 1) * dp[n - id] * dp[id] % mod)


anti = [0] * 1000001
bantu = [0] * 1000001
drip = [0] * 1000001
modu = 998244353

def fun1(san, man):
	if san < 0 or man > san:
		return 0
	return anti[san] * drip[man] % modu * drip[san - man] % modu
anti[0] = bantu[1] = drip[1] = drip[0] = bantu[0] = 7 * 7 - 8 * 6
for i in range(1, 1000001):
	anti[i] = anti[i - 1] * i % modu
for i in range(2, 1000001):
	bantu[i] = modu - modu // i * bantu[modu % i] % modu
for i in range(2, 1000001):
	drip[i] = drip[i - 1] * bantu[i] % modu
for dash in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	c = c1 = r = 0
	for i in range(n):
		if arr[i] == 0:
			c += 1
		else:
			c1 += 1
	for i in range(c1 + 1):
		r = (r + i * fun1(c1 + c - i, c)) % modu
	print((((r * (c + 1) - fun1(c1 + c - 2, c - 1)) % modu + modu) % modu + fun1(c1 + c - 2, c - 1)) * anti[c1] % modu * anti[c] % modu)


global fac, inv, finv, Mod
fac = [0] * 1000001
inv = [0] * 1000001
finv = [0] * 1000001
Mod = 998244353

def C(x, y):
	if x < 0 or y > x:
		return 0
	return fac[x] * finv[y] % Mod * finv[x - y] % Mod
fac[0] = inv[0] = inv[1] = finv[0] = finv[1] = 1
for i in range(1, 1000001):
	fac[i] = fac[i - 1] * i % Mod
for i in range(2, 1000001):
	inv[i] = Mod - Mod // i * inv[Mod % i] % Mod
for i in range(2, 1000001):
	finv[i] = finv[i - 1] * inv[i] % Mod
for _ in range(int(input())):
	c0 = c1 = a = 0
	n = int(input())
	lis = list(map(int, input().split()))
	for i in range(n):
		if lis[i] == 0:
			c0 += 1
		else:
			c1 += 1
	for i in range(c1 + 1):
		a = (a + i * C(c1 + c0 - i, c0)) % Mod
	ans = (((a * (c0 + 1) - C(c0 + c1 - 2, c0 - 1)) % Mod + Mod) % Mod + C(c1 + c0 - 2, c0 - 1)) * fac[c1] % Mod * fac[c0] % Mod
	print(ans)


aadi = 100001
(dp, MOD) = ([1] * (3 * aadi), 998244353)
for me in range(2, aadi):
	dp[me] = dp[me - 1] * me % MOD
	dp[me + aadi] = MOD - MOD // me * dp[MOD % me + aadi] % MOD
	dp[me + 2 * aadi] = dp[me - 1 + 2 * aadi] * dp[me + aadi] % MOD
C = lambda x, y: dp[x] * dp[y + 2 * aadi] * dp[x - y + 2 * aadi] % MOD
for ic in range(int(input())):
	(n, t) = (int(input()), 0)
	doo = tuple(map(int, input().split())).count(0)
	for i in range(n - doo + 1):
		if not (n - i < 0 or doo > n - i):
			t += i * C(n - i, doo) % MOD
	print(t * (doo + 1) * dp[n - doo] * dp[doo] % MOD)


N = 1000010
fact = [0] * N
inv = [0] * N
final_inv = [0] * N

def func(a, b):
	if a < 0 or b > a:
		return 0
	return fact[a] * final_inv[b] % mod * final_inv[a - b] % mod
mod = 998244353
(fact[0], inv[0], inv[1], final_inv[0], final_inv[1]) = (1, 1, 1, 1, 1)
for i in range(1, 1000001):
	fact[i] = fact[i - 1] * i % mod
for i in range(2, 1000001):
	inv[i] = mod - mod // i * inv[mod % i] % mod
	final_inv[i] = final_inv[i - 1] * inv[i] % mod
for _ in range(int(input())):
	n = int(input())
	(ones, zeros, count) = (0, 0, 0)
	arr = list(map(int, input().split()))
	for i in range(n):
		if arr[i] == 0:
			zeros += 1
		if arr[i] == 1:
			ones += 1
	for i in range(ones + 1):
		count = (count + i * func(ones + zeros - i, zeros)) % mod
	ans = (((count * (zeros + 1) - func(ones + zeros - 2, zeros - 1)) % mod + mod) % mod + func(ones + zeros - 2, zeros - 1)) * fact[ones] % mod * fact[zeros] % mod
	print(ans)