You are given an undirected graph consisting of $n$ vertices and $n$ edges, where $n$ is divisible by $6$. Each edge has a weight, which is a positive (greater than zero) integer.

The graph has the following structure: it is split into $\frac{n}{3}$ triples of vertices, the first triple consisting of vertices $1, 2, 3$, the second triple consisting of vertices $4, 5, 6$, and so on. Every pair of vertices from the same triple is connected by an edge. There are no edges between vertices from different triples.

You have to paint the vertices of this graph into two colors, red and blue. Each vertex should have exactly one color, there should be exactly $\frac{n}{2}$ red vertices and $\frac{n}{2}$ blue vertices. The coloring is called valid if it meets these constraints.

The weight of the coloring is the sum of weights of edges connecting two vertices with different colors.

Let $W$ be the maximum possible weight of a valid coloring. Calculate the number of valid colorings with weight $W$, and print it modulo $998244353$.


-----Input-----

The first line contains one integer $n$ ($6 \le n \le 3 \cdot 10^5$, $n$ is divisible by $6$).

The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 1000$) — the weights of the edges. Edge $1$ connects vertices $1$ and $2$, edge $2$ connects vertices $1$ and $3$, edge $3$ connects vertices $2$ and $3$, edge $4$ connects vertices $4$ and $5$, edge $5$ connects vertices $4$ and $6$, edge $6$ connects vertices $5$ and $6$, and so on.


-----Output-----

Print one integer — the number of valid colorings with maximum possible weight, taken modulo $998244353$.


-----Examples-----

Input
12
1 3 3 7 8 5 2 2 2 2 4 2
Output
36
Input
6
4 2 6 6 6 4
Output
2


-----Note-----

The following picture describes the graph from the first example test.

The maximum possible weight of a valid coloring of this graph is $31$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics


Solutions:
import sys
input = sys.stdin.readline
p = 998244353

def fermat_binom(n, k, p):
	if k > n:
		return 0
	num = 1
	for i in range(n, n - k, -1):
		num = num * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	return num * pow(denom, p - 2, p) % p
n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n // 3):
	test = a[i * 3:i * 3 + 3]
	test.sort()
	if test[0] == test[1]:
		if test[1] == test[2]:
			ans *= 3
			ans %= p
		else:
			ans *= 2
			ans %= p
ans *= fermat_binom(n // 3, n // 6, p)
ans %= p
print(ans)


mod = 998244353

def factor(x):
	ans = 1
	for i in range(1, x + 1):
		ans = ans * i % mod
	return ans
n = int(input())
a = list(map(int, input().split()))
d = []
ans = 1
for i in range(n // 3):
	one = a[i * 3]
	two = a[i * 3 + 1]
	three = a[i * 3 + 2]
	if one == two == three:
		ans *= 3
	elif one == two and one < three or (one == three and one < two) or (three == two and two < one):
		ans *= 2
	ans = ans % mod
n //= 3
dele = factor(n // 2)
dele = dele * dele % mod
dele = pow(dele, mod - 2, mod)
cnk = factor(n) * dele % mod
print(ans * cnk % mod)


def comb(n, r, p):
	den = 1
	num = n
	for i in range(2, r + 1):
		den = i * den % p
		num = (n - i + 1) * num % p
	return num * pow(den, p - 2, p) % p
p = 998244353
n = int(input())
w = [int(x) for x in input().split()]
ans = comb(n // 3, n // 6, p)
i = 0
while i <= n - 3:
	a = w[i]
	b = w[i + 1]
	c = w[i + 2]
	if a == b:
		if a == c:
			ans *= 3
			ans = ans % p
		elif max(a, b, c) != a:
			ans *= 2
			ans = ans % p
	elif a == c:
		if max(a, b, c) != a:
			ans *= 2
			ans = ans % p
	elif b == c:
		if max(a, b, c) != b:
			ans *= 2
			ans = ans % p
	i += 3
print(ans)


cons = 998244353
n = int(input())
temp = list(map(int, input().split()))
total = 1
for i in range(n // 3):
	(a, b, c) = (temp[3 * i], temp[3 * i + 1], temp[3 * i + 2])
	(a, b, c) = sorted([a, b, c])
	if a == b and b == c:
		total = total * 3 % cons
	elif a == b and b < c:
		total = total * 2 % cons
k = n // 3
z = n // 6
while k > z:
	total = total * k % cons
	k -= 1
while z > 0:
	total = total * pow(z, -1, cons) % cons
	z -= 1
print(total)


n = int(input())
m = n // 3
MOD = 998244353
inv = [1 for i in range(n + 1)]
for i in range(2, n + 1):
	inv[i] = inv[MOD % i] * (MOD - MOD // i) % MOD
ans = 1
for i in range(1, m // 2 + 1):
	ans *= (m + 1 - i) * inv[i]
	ans %= MOD
a = input().split()
for i in range(n):
	a[i] = int(a[i])
numMax = 0
valueMin = 0
for i in range(0, n, 3):
	valueMin = min(a[i], a[i + 1], a[i + 2])
	numMax = (a[i] == valueMin) + (a[i + 1] == valueMin) + (a[i + 2] == valueMin)
	ans *= numMax
	ans %= MOD
print(ans)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def rev_func(string):
	revstr = ''
	count = len(string) - 1
	while count >= 0:
		print('String Index: ', string[count], ' - ', count)
		revstr = revstr + string[count]
		count = count - 1
	return revstr

def mod_inverse(x, p):
	return pow(x, p - 2, p)

def comb(n, k, mod):
	result = 1
	for i in range(n - k + 1, n + 1):
		result = result * i % mod
	for i in range(2, k + 1):
		result = result * mod_inverse(i, mod) % mod
	return result
p = 998244353
n = int(input())
w = list(map(int, input().split()))
result = comb(n // 3, n // 6, p)
it = iter(w)
for (w1, w2, w3) in zip(it, it, it):
	ws = sorted([w1, w2, w3])
	if w1 == w2 == w3:
		result = result * 3 % p
	elif ws[0] == ws[1]:
		result = result * 2 % p
print(result)


import sys
input = sys.stdin.readline

def sol(arr, n):
	res = 1
	mod = 998244353
	for i in range(0, n, 3):
		mx = min(arr[i], arr[i + 1], arr[i + 2])
		cnt = 0
		if arr[i] == mx:
			cnt += 1
		if arr[i + 1] == mx:
			cnt += 1
		if arr[i + 2] == mx:
			cnt += 1
		res *= cnt
		res %= mod
	for i in range(n // 6 + 1, n // 3 + 1):
		res *= i
		res %= mod
	for i in range(1, n // 6 + 1):
		res *= pow(i, mod - 2, mod)
		res %= mod
	return res
n = int(input())
arr = list(map(int, input().split()))
print(sol(arr, n))


import bisect
from collections import defaultdict, Counter
from fractions import Fraction
import heapq
import math

def mod_inverse(x, p):
	return pow(x, p - 2, p)

def comb(n, k, mod):
	result = 1
	for i in range(n - k + 1, n + 1):
		result = result * i % mod
	for i in range(2, k + 1):
		result = result * mod_inverse(i, mod) % mod
	return result
p = 998244353
n = int(input())
w = list(map(int, input().split()))
result = comb(n // 3, n // 6, p)
it = iter(w)
for (w1, w2, w3) in zip(it, it, it):
	ws = sorted([w1, w2, w3])
	if w1 == w2 == w3:
		result = result * 3 % p
	elif ws[0] == ws[1]:
		result = result * 2 % p
print(result)


from collections import Counter
M = 998244353

def windows(it, n):
	for i in range(0, len(it), n):
		yield tuple(it[i:i + n])
res = 1
n = int(input())
edges = list(map(int, input().split()))
for weights in windows(edges, 3):
	if len(set(weights)) == 1:
		res *= 3
	elif len(set(weights)) == 2 and Counter(weights)[max(weights)] == 1:
		res *= 2
k = n // 6
for x in range(1, k + 1):
	res = res * (x + k) * pow(x, M - 2, M) % M
print(res)


import math

def getExponent(base, exponent, modulo):
	if exponent == 0:
		return 1
	p = getExponent(base, exponent // 2, modulo) % modulo
	p = p * p % modulo
	if exponent % 2 == 0:
		return p
	else:
		return base * p % modulo

def modInverse(value, modulo):
	return getExponent(value, modulo - 2, modulo)
numCases = int(input())
hold = input().split()
values = [int(i) for i in hold]
current = []
ways = 1
for i in range(len(values)):
	if i % 3 == 0 and i != 0:
		current.sort()
		if current[0] == current[1] and current[1] == current[2]:
			ways *= 3
		elif current[0] == current[1]:
			ways *= 2
		else:
			ways *= 1
		current = []
	current.append(values[i])
current.sort()
if current[0] == current[1] and current[1] == current[2]:
	ways *= 3
elif current[0] == current[1]:
	ways *= 2
else:
	ways *= 1
graphs = numCases / 3
graph2 = graphs / 2
inv1 = modInverse(math.factorial(int(graph2)), 998244353)
print(ways * inv1 * inv1 * math.factorial(int(graphs)) % 998244353)


n = int(input())
p = list(map(int, input().split()))
do = 0
tr = 0
m = int(n // 3)
v = int(n // 6)
for i in range(0, n, 3):
	d = p[i:i + 3]
	d.sort()
	if d[0] == d[1] == d[2]:
		tr += 1
	elif d[0] == d[1]:
		do += 1
import math
gh = math.factorial(m) // math.factorial(v) ** 2 * 3 ** tr * 2 ** do % 998244353
print(int(gh))


import math

def nCr(n, r):
	return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
n = int(input())
l1 = list(map(int, input().split()))
i = 0
ans = 1
x = 998244353
while i < n:
	l2 = l1[i:i + 3]
	l2.sort()
	if l2[0] == l2[1] and l2[1] != l2[2]:
		ans = ans * 2 % x
	elif l2[0] == l2[1] and l2[1] == l2[2]:
		ans = ans * 3 % x
	i += 3
ans = ans * (nCr(int(n / 3), int(n / 6)) % x) % x
print(int(ans))


import math
a = int(input())
b = input().split()
n = 998244353
wt = 1
for x in range(0, a, 3):
	d = int(b[x])
	e = int(b[x + 1])
	f = int(b[x + 2])
	k = [d, e, f]
	k.sort()
	if d == e and e == f:
		wt = 3 * wt
	elif k[0] == k[1] and k[1] != k[2]:
		wt = 2 * wt
wt = wt % n
q = a // 3
w = a // 6
y = math.factorial(q) // math.factorial(w) ** 2 % n
print(int(y * wt % n))


from math import factorial as f
n = int(input())
arr = list(map(int, input().split()))
p = 1
for a in zip(arr[::3], arr[1::3], arr[2::3]):
	p *= a.count(min(a))
print(f(n // 3) // f(n // 6) ** 2 * p % 998244353)


import math
mod = 998244353
n = int(input())
t1 = math.factorial(n // 3)
t2 = math.factorial(n // 6)
ans = t1 // t2 ** 2
ans %= mod
data = list(map(int, input().split()))
for i in range(0, n, 3):
	a = data[i]
	b = data[i + 1]
	c = data[i + 2]
	mini = min(a, min(b, c))
	temp = 0
	if a == mini:
		temp += 1
	if b == mini:
		temp += 1
	if c == mini:
		temp += 1
	ans *= temp
print(int(ans % mod))


import math
f = lambda x: math.factorial(x)
n = int(input())
arr = list(map(int, input().split()))
i = 0
ans = 1
while i + 2 < n:
	t = sorted(arr[i:i + 3])
	ans *= 3 if t[0] == t[1] == t[2] else 2 if t[0] == t[1] else 1
	i += 3
print(f(n // 3) // (f(n // 6) * f(n // 6)) * ans % 998244353)


from math import factorial as fact
n = int(input())
lst = list(map(int, input().split()))
p = 1
for i in range(0, n - 2, 3):
	(a, b, c) = (lst[i], lst[i + 1], lst[i + 2])
	if a == b == c:
		p *= 3
		continue
	if a != b and b != c and (a != c):
		continue
	seg = lst[i:i + 3]
	if seg.count(max(seg)) == 2:
		continue
	if seg.count(min(seg)) == 2:
		p *= 2
		continue
x = n // 3
h = n // 6
num = fact(x)
deno = fact(h) * fact(h)
p *= int(num // deno)
print(p % 998244353)


import math
mod = 998244353
n = int(input())
l = list(map(int, input().split()))
ans = 1
d = {}
q = 1001
for i in range(0, n):
	if l[i] in d:
		d[l[i]] += 1
	else:
		d[l[i]] = 1
	q = min(q, l[i])
	if i % 3 == 2:
		ans = ans * d[q]
		d = {}
		q = 1001
n = n // 3
r = math.factorial(n)
s = math.factorial(n // 2)
s = s * s
r = r // s
r = r
ans = ans * r
ans = ans % mod
print(ans)


import math
import sys
f = lambda x: math.factorial(x)
n = int(sys.stdin.readline())
arr = list(map(int, input().split()))
i = 0
ans = 1
while i + 2 < n:
	t = sorted(arr[i:i + 3])
	ans *= 3 if t[0] == t[1] == t[2] else 2 if t[0] == t[1] else 1
	i += 3
sys.stdout.writelines(str(f(n // 3) // (f(n // 6) * f(n // 6)) * ans % 998244353) + '\n')


a = int(input())
size = int(a / 3)
b = list(map(int, input().split()))
m = 0
vi = []
import math
f = lambda x: math.factorial(x)

def prod_list(li, size):
	a = 1
	for i in range(size):
		a = a * li[i]
	return a
for j in range(size):
	temp = []
	for i in range(m, m + 3):
		temp.append(b[i])
	vi.append(temp)
	m += 3
ans_prod = 1
for t in range(size):
	h = set(vi[t])
	if len(h) == 1:
		ans_prod = ans_prod * 3
	elif len(h) == 2:
		vi[t].sort()
		if vi[t][0] == vi[t][1]:
			ans_prod = ans_prod * 2
ans_prod = ans_prod * (f(size) // (f(size // 2) * f(size // 2)))
print(ans_prod % 998244353)