Problem:
 Score : 300 points    Problem Statement Given is an integer sequence D_1,...,D_N of N elements. Find the number, modulo 998244353 , of trees with N vertices numbered 1 to N that satisfy the following condition:   For every integer i from 1 to N , the distance between Vertex 1 and Vertex i is D_i .       Notes  A tree of N vertices is a connected undirected graph with N vertices and N-1 edges, and the distance between two vertices are the number of edges in the shortest path between them.  Two trees are considered different if and only if there are two vertices x and y such that there is an edge between x and y in one of those trees and not in the other.       Constraints  1 \leq N \leq 10^5  0 \leq D_i \leq N-1         Input Input is given from Standard Input in the following format:  N  D_1  D_2  ...  D_N       Output Print the answer.        Sample Input 1 4
0 1 1 2      Sample Output 1 2  For example, a tree with edges (1,2) , (1,3) , and (2,4) satisfies the condition.       Sample Input 2 4
1 1 1 1      Sample Output 2 0       Sample Input 3 7
0 3 2 1 2 2 1      Sample Output 3 24

Solution (Python):
from collections import Counter
import sys
N = int(input())
D = [int(i) for i in input().split()]
if D[0] != 0:
    print(0)
    sys.exit()
D.sort()
if D[1] == 0:
    print(0)
    sys.exit()
a = Counter(D)
a = dict(sorted(a.items(), key=lambda x:x[0]))
ans = 1
mod = 998244353
backnumber = 1
for i, (x, y) in enumerate(a.items()):
    if i != x:
        print(0)
        sys.exit()
    if i != 0:
        ans *= backnumber**y
        ans = ans % mod
    backnumber = y
print(ans)

Solution (Python):

import collections

N = int(input())
D = list(map(int,input().split()))

set_D = set(D)
c = collections.Counter(D)

sum = 1
if D[0] != 0 or D.count(0) > 1:
  print(0)
elif len(set_D)-1 == max(set_D):
  for i in range(len(set_D)):
    if i >= 1:
      sum *= c[i-1]**c[i]
  q, mod = divmod(sum, 998244353)
  print(mod)
else:
  print(0)

Solution (Python):
import collections
def counter_list(A):
  counter = collections.Counter(A)
  counter =  [list(e) for e in counter.items()]
  counter.sort() 
  return counter

N = int(input())
D = list(map(int,input().split()))



if(D[0] != 0): ans = 0 
else: 
  D = counter_list(D) 
  if(D[0][1] != 1):
    ans = 0
  else:
   ans = 1
   for i in range(len(D)-1):
      if(D[i+1][0] - D[i][0] != 1):
        ans = 0
        break
      a = D[i][1]%998244353
      b = D[i+1][1]
      ans = ans%998244353
      ans = ans*(a**b)
      ans = ans%998244353
print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

mod = 998244353
from collections import Counter

def main():
  n = ni()
  d = na()

  if d[0] != 0:
    print(0)
    return
  
  pre = 0
  for dd in set(d[1:]):
    if dd - pre > 1 or dd == 0:
      print(0)
      return
    pre = dd

  dic = {}
  for dd in d:
    if dd in dic:
      dic[dd] += 1
    else:
      dic[dd] = 1

  ans = 1
  t = sorted(dic.items(), key = lambda x: x[0])
  for i in range(1, len(t) - 1):
    x = (t[i][1] ** t[i+1][1]) % mod
    ans *= x
    ans %= mod
  print(ans % mod)
 

if __name__ == '__main__':
  main()

Solution (Python):
import numpy as np
import collections
import sys
N  = int(input())
Ds = np.array(list(map(int, input().split(' '))))
if Ds[0] != 0:
    print(0)
    sys.exit()
if np.any(Ds[1:] == 0):
    print(0)
    sys.exit()

uniq = np.unique(Ds)
uniq.sort()

if not np.all(uniq == np.arange(uniq.min(), uniq.max() + 1)):
    print(0)
    sys.exit()
C = collections.Counter(Ds)
counts = 1
for i in range(1, uniq.max() + 1):
    counts *= C[i-1] ** C[i]
print(counts % 998244353)

Solution (Python):
mod = 998244353
n = int(input())
A = [int(x) for x in input().split()]

if A[0] != 0:
    print(0)
else:
    L = [0]*(n+1)
    for i in range(n):
        L[A[i]] += 1

    if L[0]!=1:
        print(0)
    else:
        ans = 1
        for i in range(1,n+1):
            if L[i]>0:
                for k in range(L[i]):
                    ans *= L[i-1]
                    ans %= mod
            else:
                nxt = i
                break
        for j in range(nxt,n+1):
            if L[j] != 0:
                print(0)
                break
        else:
            print(ans)

Solution (Python):
N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
else:
    D = D[1:]
    C = [0]*N
    m = max(D)
    for d in D:
        C[d] += 1
    if C[0] != 0 or 0 in C[1: m + 1]:
        print(0)
    else:
        res = 1
        i = 1
        for i in range(1, m):
            res *= (C[i]**C[i + 1])%998244353
        print(res%998244353)

Solution (Python):
from sys import stdin

N = int(stdin.readline().rstrip())
D = [int(x) for x in stdin.readline().rstrip().split()]

if D[0] > 0:
    print(0)
    exit()
D.sort()

ans = 1
mod = 998244353
b = 1

temp = 1
for i in range(1, N):
    if D[i] == 0:
        print(0)
        exit()
    if D[i] - D[i - 1] > 1:
        print(0)
        exit()
    if D[i] != D[i - 1]:
        b = temp
        temp = 1
    else:
        temp += 1
    ans *= b
    ans %= mod

print(ans % mod)

Solution (Python):
from collections import Counter

N = int(input())
D = list(map(int, input().split()))

if D.pop(0):
  print(0)
else:
  C = Counter(D)
  if 0 in C:
    print(0)
  else:
    count = 1
    for i in range(2, max(C)+1):
      if i not in C:
        print(0)
        break
      count *= C[i-1]**C[i]
      count %= 998244353
    else:
      print(count)

Solution (Python):
from collections import Counter
n = int(input())
D = list(map(int, input().split()))
p = 998244353

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

count_dict = sorted(Counter(D).items(), key=lambda x:x[0])
count_list = list(dict(count_dict).values())

if len(count_list) == max(D) + 1 and not 0 in D[1:]:
    ans = 1
    for i in range(len(count_list)):
        if i == 0:
            if D[0] == 0:
                pass
            else:
                ans = 0
                break
        else:
            ans *= power_func(count_list[i - 1], count_list[i], p)
else:
    ans = 0

ans %= p
print(ans)

Solution (Python):
N = int(input())
D = list(map(int, input().split()))
c = [0]*(N + 1)
a = 0
ans = 1
temp = 0
pre = 1
mod = 998244353
c = 1

if D[0] != 0:
    print(0)
    a = 1

if a == 0:
    D = sorted(D)
    for i, d in enumerate(D):
        if i == 0:
            continue
        if d == 0:
            print(0)
            a = 1
            break
        if temp != d:
            if (d - temp) != 1:
                print(0)
                a = 1
                break
            ans *= pre ** c

            temp = d
            pre = c
            c = 1
        else:
            c += 1

        if i == N-1:
            ans *= pre ** c
    if a == 0:
        print(ans%mod)

Solution (Python):
_,*D=map(int,open(0).read().split());a=D[0]<1;M=[0]*-~max(D)
for d in D:M[d]+=1
for m,n in zip(M,M[1:]):a*=m**n
print((M[0]<2)*a%998244353)

Solution (Python):
n= int(input())
d= list(map(int, input().split()))
y=(d[0]!=0)
d.sort()
x=[0]*(d[n-1]+1)
k=0
ans=False
for i in range(n):
    if d[i]==k:
        x[k]+=1
    elif d[i]==k+1:
        k+=1
        x[k]+=1
    else:
        ans=True
    


if ans or x[0]>=2 or y:
    print(0)
else:
    a=1
    for i in range(d[n-1]):
        a*=(x[i]**x[i+1])
    print(a%998244353)

Solution (Python):
from collections import Counter

N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
    exit()
D.sort()
count = Counter(D)
if count[0] != 1:
    print(0)
    exit()
ans = 1
for i in range(1, D[-1] + 1):
    if i not in count:
        print(0)
        exit()
    ans *= count[i-1] ** count[i]
print(ans % 998244353)

Solution (Python):
d = 998244353

num = int(input())

l = list(map(int, input().split()))


flag = True

if l[0] != 0:
  flag = False

ll = set(l)

for i in range(max(ll)):
  if i + 1 not in ll:
    flag = False

a = [0 for i in range(max(ll))]

for x in l[1:]:
  if x == 0:
    flag = False
    break
  a[x-1] += 1


ans = 1

for i in range(len(a)-1):
  ans *= a[i] ** a[i+1]


if flag:
  print(ans % d)
else:
  print(0)

Solution (Python):
N = int(input().strip())
D = list(map(int, input().strip().split(" ")))
d = list(set(D))

if D[0] != 0:
    print(0)
    exit()
if min(d) > 0 or max(d) >= len(d):
    print(0)
    exit()

c = 1
x = [0] * len(d)
for i in D:
    x[i] += 1
if x[0] != 1:
    print(0)
    exit()
for i in range(1,len(d)):
    c *= x[i-1]**x[i]

print(c % 998244353)

Solution (Python):
_,*D=map(int,open(0).read().split());a=1;M=[0]*-~max(D)
for d in D:M[d]+=1
for m,n in zip(M,M[1:]):a*=m**n
print((D[0]<1)*(M[0]<2)*a%998244353)

Solution (Python):
n = int(input())
d = [int(i) for i in input().split()]
a = sorted(d)
checkZero = False
if(d[0] != 0):
    checkZero = True
for i in range(1,len(d)):
    if(d[i] == 0):
        checkZero = True

if(checkZero):
    print(0)
else:
    start = 0
    counta = 0
    countb = 1
    ans = 1
    for i in a:
        if(start == i):
            counta += 1
        elif(i - start > 1):
            ans = 0
        else:
            ans *= countb ** counta
            start = i
            countb = counta
            counta = 1
    ans *= countb ** counta
    print(ans%998244353)

Solution (Python):
n = int(input())
d = [int(x) for x in input().split(' ')]

m = {}
for item in d:
    if item in m:
        m[item] += 1
    else:
        m[item] = 1

if d[0] == 0 and m[0] == 1:
    prev = 1
    s = 1
    visited = 1
    for i in range(1, 10 ** 5):
        if not i in m:
            break
        v = m[i]
        visited += v

        s *= (prev ** v)
        s = s % 998244353
        prev = v
    if visited != n:
        s = 0
else:
    s = 0

print(s)

Solution (Python):
N=int(input())
D=list(map(int,input().split()))

mod=998244353

if D[0]!=0:
    print(0)
    exit()

n=[0]*N
n[0]=1
for i in range(1,N):
    if D[i]==0:
        print(0)
        exit()
    n[D[i]]+=1

ans=1
cnt=n[0]+n[1]
for i in range(2,N):
    if n[i]==0:
        if cnt!=N:
            print(0)
            exit()
        else:
            break
    ans=ans*n[i-1]**n[i]
    ans=ans%mod
    cnt=cnt+n[i]
print(ans)

Solution (Python):
M = 998244353

N = int(input())
d_list = list(map(int, input().split()))

def check():
	if d_list[0] != 0:
		print(0)
		return
	d_list.sort()
	d_counts = []
	prev_d = -1
	for d in d_list:
		if prev_d == d:
			d_counts[prev_d] += 1
		elif prev_d + 1 == d:
			d_counts.append(1)
			prev_d = d
		else:
			print(0)
			return
	count = 1
	prev_c = d_counts.pop(0)
	if prev_c != 1:
		print(0)
	else:
		for c in d_counts:
			count = (count * pow(prev_c, c, M)) % M
			prev_c = c
		print(count)

check()

Solution (Python):
n=int(input())
d=list(map(int,input().split()))

if d[0] != 0:
  print(0)
  exit()

ans=1

a=[0]*(n+1)

for i in d:
  a[i] += 1

if a[0] != 1:
  print(0)
  exit()

for j in range(n):
  if j!=0 and a[j] == 0:
    for k in range(j+1,n):
      if a[k] != 0:
        print(0)
        exit()
    break
  else:
    ans*=(a[j]**a[j+1])
    ans%=998244353

print(ans)

Solution (Python):
import sys
n=int(input())
d=list(map(int,input().split()))
if d[0]!=0:
    print(0)
    sys.exit()
d.sort()
mx=d[-1]
count=[0]*(mx+1)
MOD=998244353
for i in range(n):
    count[d[i]]+=1
c=1

if count[0]!=1:
    print(0)
    sys.exit()
for i in range(1,mx+1):
    c*=pow(count[i-1],count[i],MOD)
    c%=MOD
print(c)

Solution (Python):
N = int(input())
D = list(map(int, input().split()))
mod = 998244353
mN = max(D)
count = [0] * (mN + 1)
for i in range(N):
    count[D[i]] += 1
if count[0] != 1 or D[0] != 0:
    print(0)
elif mN == 0:
    print(1)
else:
    ans = 1
    for i in range(1, len(count)):
        if count[i]:
            ans = (ans * (count[i - 1] ** count[i])) % mod
        else:
            print(0)
            exit()
    print(ans)

Solution (Python):
from collections import Counter

N = int(input())
D = list(map(int, input().split()))
if D[0] != 0: 
    print(0)
    exit()
    
D = Counter(D)

ans = 1
if D[0] > 1: 
    print(0)
    exit()

for i in range(N):
    ans = (ans * D[i] ** D[i+1]) % 998244353

print(ans)

Solution (Python):
from collections import Counter
N = int(input())
D = list(map(int,input().split()))
if D[0] != 0:
    print(0)
    exit()
D = D[1:]
DD = Counter(D)
if DD[0] != 0:
    print(0)
    exit()

MOD = 998244353
ans = 1
if len(DD) == 1:
    print(1)
    exit()
for i in range(2,len(DD)+1):
    ans *= pow(DD[i-1],DD[i],MOD)
    ans %= MOD
print(ans)

Solution (Python):
from collections import Counter


def resolve():
    n = int(input())
    d = list(map(int, input().split()))
    c = Counter(d)
    m = sorted(c)[-1]
    ans = 1
    if d[0] != 0 or c[0] != 1:
        print(0)
        return
    for i in range(1, m + 1):
        if not i in c:
            print(0)
            return
        ans *= c[i - 1] ** c[i]
        ans %= 998244353
    print(ans)


if __name__ == '__main__':
    resolve()

Solution (Python):
N = int(input())
D = [int(i) for i in input().split()]

key = max(D) + 1
count_list = [0] * key

for i in range(N):
    count_list[D[i]] += 1

counter = 1
if 0 in count_list:
    counter = 0

if count_list[0] != 1:
    counter = 0

if D[0] != 0:
    counter = 0 

for i in range(1, key - 1):
    counter *= count_list[i]**count_list[i + 1]

print(counter%998244353)

Solution (Python):
n = int(input())
d = list(map(int, input().split()))

if d[0] != 0:
    print(0)
    exit()

d.sort()

if d[1] != 1:
    print(0)
    exit()

i = 1
dis = 1
sep = [0] * (10 ** 5)
sep[0] = 1
ans = 1
while i < n:
    if d[i] != dis:
        print(0)
        exit()
    while i < n and d[i] == dis:
        sep[dis] += 1
        i += 1
    ans *= sep[dis-1] ** sep[dis]
    ans %= 998244353
    dis += 1
print(ans)

Solution (Python):
from collections import defaultdict
N = int(input())
D = list(map(int, input().split()))
if D[0] > 0:
    print(0)
    exit()

D = D[1:]
for d in D:
    if d == 0:
        print(0)
        exit()

mod = 998244353
X = defaultdict(int)

for d in D:
    X[d] += 1

M = max(D)
ans = 1
for i in range(1, M):
    if X[i] == 0:
        ans = 0
        break
    ans *= pow(X[i], X[i+1], mod)
    ans %= mod
print(ans%mod)

Solution (Python):
N=int(input())
E=list(map(int, input().split()))
k=max(E)
D={}
for i in range(k+1):
    D[i]=0
for i in range(N):
    D[E[i]]+=1
    

ans=1
for i in range(1,k+1):
    ans*=D[i-1]**D[i]
if D[0]==1 and E[0]==0:
    print(ans%998244353)
else:
    print(0)

Solution (Python):
from collections import Counter

N = int(input())
Dlist = list(map(int, input().split()))

INF = 998244353

if Dlist[0] != 0:
    print(0)

else:
    D_max = max(Dlist)
    cnt = [0] * (D_max + 1)

    dic = Counter(Dlist)
    for k, v in dic.items():
        cnt[k] = v

    ans = cnt[0]

    if ans != 1:
        print(0)

    else:
        for i in range(D_max):
            ans = ans * (((cnt[i] % INF) ** cnt[i+1]) % INF)
            ans = ans % INF
        
        print(ans % INF)

Solution (Python):
import bisect

n = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
  print(0)
else:
  c = 1
  temp = 1
  e = 1
  D.sort()
  m = D[-1]
  if n > 1 and D[1] == 0:
    print(0)
    exit()
  else:
    for i in range(1, m+1):
      a = bisect.bisect_right(D, i)
      d = a - temp
      temp = a
      if d == 0 and i>0:
        print(0)
        exit()
      else:
        c *= e**d
        c %= 998244353
        e = d
    print(c)

Solution (Python):
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        D = list(map(int, input().split()))

        if D[0] != 0:
            print(0)
            exit()
        D = D[1:]
        D.sort()

        if D[0] == 0:
            print(0)
            exit()

        cnt = []
        before = 0
        for d in D:
            if d > before + 1:
                print(0)
                exit()
            else:
                if len(cnt) == d - 1:
                    cnt.append(1)
                else:
                    cnt[-1] += 1
                before = d

        ans = 1
        for i, v in enumerate(cnt):
            if i > 0:
                ans *= (cnt[i - 1]) ** v
        print(ans % 998244353)



if __name__ == '__main__':
    AtCoder().main()

Solution (Python):
N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
    exit()
import collections
cnt = collections.Counter(D[1:])
if 0 in cnt:
    print(0)
    exit()
maxs = 998244353
res = 1
flag = True
scnt = sorted(cnt.items(), key=lambda x: x[0])
if scnt[0][0] != 1:
    print(0)
else:
    for i in range(1, len(scnt)):
        if scnt[i][0] != scnt[i-1][0] + 1:
            flag = False
            break
        
        res = (res * (scnt[i-1][1] ** scnt[i][1])) % maxs
        
    print(res) if flag else print(0)

Solution (Python):
N = int(input())
D = list(map(int,input().split()))

if D[0] != 0:
    print(0)
    exit(0)
    
max_D = max(D)
    
c = [0] * (max_D+1)
for i in range(N):
    c[D[i]] += 1
   

if c[0] > 1:
    print(0)
    exit(0)
   
ans = 1 
for i in range(max_D):
    ans *= c[i] ** c[i+1]
print(ans % 998244353)

Solution (Python):
n = int(input())
d = list(map(int, input().split()))

if d[0] != 0:
    print(0)
    exit()

d.sort()

if n == 1:
    if d[0] == 0:
        print(1)
    else:
        print(0)
    exit()

if d[0] != 0 or d[1] != 1:
    print(0)
    exit()


mini = d[0]
maxi = d[-1]
num = 1
cnt = 0
lst = [1]
for i in d[1:]:
    if i == num:
        cnt += 1
    elif i == num+1:
        lst.append(cnt)
        num = i
        cnt = 1
    else:
        print(0)
        exit()

lst.append(cnt)

ans = 1
for i in range(1, len(lst)-1):
    ans = (ans * lst[i]**lst[i+1]) % 998244353

print(ans)

Solution (Python):
N = int(input())
D = [int(d) for d in input().split()]

f = 0
if D[0] != 0:
    f = -1
mod = 998244353
L = []

num = 0
cnt = 0
D.sort()
for i in range(N):
    if D[i] == num:
        cnt += 1
    elif D[i] == num+1:
        L.append(cnt)
        cnt = 1
        num += 1
    else:
        f = -1
        break
        
L.append(cnt)
ans = 1
if f == 0:
    if D[0] != 0:
        ans = 0
    if N > 1:
        if D[1] != 1:
            ans = 0
    if ans > 0:
        for i in range(1, len(L)):
            ans *= L[i-1]**L[i]
            ans %= mod
else:
    ans = 0
    
print(ans)

Solution (Python):
import sys
import collections
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
N = int(input())
D = list(map(int, input().split()))
mD = max(D)

c = collections.Counter(D)
c = dict(c)

ans = 1
tmp = 1
for i in range(mD+1):
    if not(i in c.keys()):
        ans = 0
        break
    elif i == 0:
        if c[0] > 1:
            ans = 0
            break
    elif i == 1:
        tmp = c[i]
    else:
        ans = (ans * tmp**c[i])%MOD
        tmp = c[i]

if D[0] != 0:
    print(0)
else:
    print(ans)

Solution (Python):
from itertools import groupby
N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
    exit()
D = groupby(sorted(D))
t = 998244353

ans = 1
pre = 0
cur = 0
for i, d in D:
    if i != cur:
        print(0)
        exit()
    else:
        cur += 1
    l = len(list(d))
    if i == 0 and l > 1:
        print(0)
        exit()
    if i <= 1:
        pre = l
        continue
    ans = ans * (pre**l)
    pre = l

print(ans % t)

Solution (Python):
N = int(input())
D = list(map(int, input().split()))
d = [0 for _ in range(max(D)+1)]
mod = 998244353
for i in D:
    d[i] += 1
if D[0] != 0 or d[0] != 1 or d.count(0) > 0:
    print(0)
else:
    ans = 1
    for i in range(len(d)-1):
        ans *= d[i]**d[i+1]%mod
    print(ans%mod)

Solution (Python):
def main():
    n = int(input())
    l = {}
    o = list(map(int, input().split()))
    if o[0] != 0:
        print(0)
        exit()
    for i in o:
        if i in l:
            l[i] += 1
        else:
            l[i] = 1
    
    count = 1
    m = max(l)
    if 0 not in l:
        print(0)
        exit()
    if l[0] >= 2:
        print(0)
        exit()
    
    for i in range(1,m+1):
        if i in l:
            count *= l[i-1] ** l[i] % 998244353
        else:
            print(0)
            exit()
    
    print(count%998244353)


if __name__ == '__main__':
    main()

Solution (Python):
import collections
import sys
n = int(input())
d = list(map(int, input().split()))
c = collections.Counter(d)
if d[0] != 0 or c[0] > 1:
    print(0)
    sys.exit()
ans = 1
end = max(c.keys())
for i in range(2, end+1):
    if ans == 0:
        break
    ans *= c[i-1]**c[i]
print(ans % 998244353)

Solution (Python):
N = int(input())
Ds = list(map(int, input().split()))
if Ds[0] != 0:
  print(0)
  exit()
Ns = [0]*N
for D in Ds:
  Ns[D] += 1

if Ns[0] != 1:
  print(0)
  exit()
r = 1
p = 1
for n in Ns:
  
  for i in range(n):
    r = r*p%998244353
  p = n
print(r)

Solution (Python):
n=int(input())
d=list(map(int,input().split()))
num=[0 for i in range(n)]
ans=1
flag=0
for i in d:
  num[i]+=1
if d[0]>=1:
  ans=0
else:
  for i in range(1,n-1):
      ans*=num[i]**num[i+1]
      while ans>998244353:
        ans=ans%998244353
for i in range(1,n):
  if d[i]==0 and ans>0:
    ans=0




print(ans)

Solution (Python):
n = int(input())
d = list(map(int,input().split()))
mod =  998244353

cnt = [0]*n

if d[0] != 0:
    print(0)
    exit()

for e in d:
    cnt[e] += 1

if cnt[0] != 1:
    print(0)
    exit()

res = 1
for i in range(1,n):
    if cnt[i] != 0:
        if cnt[i-1] == 0:
            print(0)
            exit()
        res = res*pow(cnt[i-1],cnt[i],mod)%mod

print(res%mod)

Solution (Python):
import heapq
mod = 998244353
n = int(input())
d = list(map(int, input().split()))
q = []
if d[0] != 0:
  print(0)
else:
  for x in d[1:]:
    heapq.heappush(q, x)
  prev = 0
  x = 0
  y = 1
  ans = 1
  for i in range(n-1):
    a = heapq.heappop(q)
    if a == 0:
      print(0)
      break
    elif a == prev:
      x += 1
    elif a == prev + 1:
      x += 1
      ans = ans * (y ** x) % mod
      y = x
      x = 0
    else:
      print(0)
      break
    prev = a
  else:
    x += 1
    ans = ans * (y ** x) % mod
    print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines


import math





















def main():
	n=int(input())
	D=list(map(int,input().split()))
	
	
	if D[0]!=0:
		print(0)
		exit(0)
	
	if len(D)==1:
		print(1)
		exit(0)
		
		
	D.sort()
	
	if D[1]!=1:
		print(0)
		exit(0)
	
	ans=1
	
	li=[0]*n
	
	for i in range(n):
		li[D[i]]+=1
	
	for i in range(1,n):
		ans*=li[D[i]-1]
		ans%=998244353
	
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import sys
input=sys.stdin.readline

n=int(input())
d=list(map(int,input().split()))

if d[0]!=0:
  print(0)
  exit()

 
maxd=max(d)
kyori=[0]*(maxd+1)


for i in d:
  kyori[i]+=1


if kyori[0]!=1:
  print(0)
  exit()

ans=1
for i in range(1,maxd):
  temp=kyori[i]**kyori[i+1]
  ans*=temp%998244353
  ans=ans%998244353
print(ans)

Solution (Python):
N = int(input())
D = list(map(int,input().split()))
BIGNUM = 998244353

ans = 1

if D[0] != 0:
    ans = 0
distance_dict = {0:1}
for i in D[1:]:
    if not i in distance_dict:
        distance_dict[i] = 1
    else:
        distance_dict[i] += 1




if distance_dict[0] != 1:
    print(0)
    exit()

for i in range(1,max(distance_dict.keys())+1):
    if not i in distance_dict: 
        ans = 0
        print(0)
        exit()

    elif i != 0:
        ans *= (distance_dict[i-1]**distance_dict[i]) 
print(ans%BIGNUM)

Solution (Python):

from collections import Counter
mod = 998244353
n = int(input())
dli = list(map(int, input().split()))
for ind in range(len(dli)):
    if (ind == 0):
        if (dli[ind] != 0):
            print(0)
            exit()
    else:
        if (dli[ind] == 0):
            print(0)
            exit()

count = Counter(dli)

for ind, key in enumerate(count.keys()):
    if ind != key:
        print(0)
        exit()

sort = sorted(count.items(), key=lambda x:x[0])

tmp = []
for ind in range(len(sort)-1):
    mae = sort[ind][1]
    next = sort[ind+1][1]

    tmp.append(int(mae**next))

total = 1
for t in tmp:
    total *= t
print(total%mod)

Solution (Python):
N = int(input())
Dn = list(map(int,input().split(' ')))

previous_num = 0
previous_cnt = 1
current_num = 0
sum_num = 1
flag = False
output_list = [0]* N
max_num = 0
if Dn[0] == 0:
    output_list[0] = 1
    for i in range(1,N):
        max_num = max(max_num,Dn[i]) 
        output_list[Dn[i]] +=1


    '''
    for i in range(1,N):
        if Dn[i] == previous_num + 1:
            current_num += 1
        elif Dn[i] == previous_num + 2:
            if previous_num > 0:
                sum_num = sum_num * (previous_cnt**current_num)
            previous_cnt = current_num
            previous_num += 1
            current_num = 1
        else:
            flag = True
            break
        if i == N-1:
            if previous_num > 0:
                sum_num = sum_num * (previous_cnt**current_num)
    if flag:
        print(0)
    else:
        print(sum_num%998244353)
    '''
    if output_list[0] !=1:
        print(0)
    else:
        for i in range(2,max_num+1):
            sum_num = sum_num * (output_list[i-1]**output_list[i])
        print(sum_num%998244353)
else:
    print(0)

Solution (Python):
MOD = 998244353

def beki(x, n):
  if n == 0:
    return 1
  if n % 2 == 0:
    return beki(x * x % MOD, n // 2) % MOD
  else:
    return x * beki(x, n - 1) % MOD


N = int(input())
Orig = list(map(int, input().split()))
D = sorted(Orig)

ans = 1
cnt = 1
precnt = 1

if Orig[0] != 0:
    ans = 0
if N >= 2 and D[1] == 0:
    ans = 0

for i in range(N-1):
    if D[i] == D[i+1]:
        cnt += 1

    elif D[i] + 1 != D[i+1]:
        ans = 0
        break

    else:
        ans *= beki(precnt, cnt)
        ans %= MOD
        precnt = cnt
        cnt = 1
        if (i == N-1):
            break
else:
    ans *= beki(precnt, cnt)
    ans %= MOD

print(ans)

Solution (Python):
p=998244353
n=int(input())

a=list(map(int,input().split()))

kanou=True

if(a[0]!=0):
    print(0)
    kanou=False

a.sort()



cnt=[0]*n

if(kanou):
    if(n==1):
        if(a[0]==0):
            print(1)
        else:
            print(0)
        kanou=False
    elif(a[0]!=0 or a[1]==0):
        print(0)
        kanou=False



if(kanou):
    cnt[0]=1
    temp=0
    for c in a:
        if(c==0):
            continue
        if(c==temp):
            cnt[c]+=1
        elif(c==temp+1):
            cnt[c]+=1
            temp+=1
        else:
            kanou=False
            print(0)
            break


ans=1
if(kanou):
    for i in range(1,n):
        if(cnt[i]==0):
            break
        ans*=cnt[i-1]**cnt[i]
        ans%=p

    print(ans)

Solution (Python):
def listConvert(baseList):
  maxNum = max(baseList)
  newList = [0] * (maxNum + 1)
  for a in baseList:
    newList[a] += 1
  return newList

def mainFunc(baseList):
  if baseList[0] != 0:
    return 0

  newList = listConvert(baseList)
  if newList[0] > 1:
    return 0
  if newList.count(0) > 0:
    return 0

  result = 1
  preA = 1
  mod = 998244353
  for a in newList:
    result = (result * pow(preA, a)) % mod
    preA = a
  return result

n = int(input())
baseList = list(map(int, input().split()))

print(mainFunc(baseList))

Solution (Python):
import collections
n = int(input())
d = list(map(int, input().split()))
fl = False
if d[0] != 0:
  fl = True
  print(0)
else:
  del d[0]
  c = collections.Counter(d)
  ll = len(c)
  ans = 1
  for i in range(1, ll+1):
    if c[i] == 0:
      print(0)
      fl = True
      break
    else:
      if i != 1:
        ans *= c[i-1]**c[i]

if not fl:
  print(ans%998244353)

Solution (Python):
from collections import Counter
N = int(input())
D = list(map(int, input().split()))
MOD = 998244353

def calc():
    if D[0] != 0:
        return 0
    if sum(D) < N-1:
        return 0
    
    c = Counter(D)
    ret = 1
    tmpkey = 0
    tmpvalue = 0
    for key in sorted(c.keys()):
        if key - tmpkey >= 2:
            return 0
        if key == 0:
            if c[key] >= 2:
                return 0
        else:
            ret *= (tmpvalue ** c[key]) % MOD
            ret %= MOD
        tmpkey = key
        tmpvalue = c[key]
    return ret

print(calc())

Solution (Python):
valid = True
n = int(input())
ds = [int(i) for i in input().split()]
if(ds[0]!=0):
    valid = False
    print(0)
ds.sort()
count = []
c = 1
for i in range(len(ds)-1):
    if(not i==0 and ds[i]==0):
        valid = False
        print(0)
        break
    if(ds[i]==ds[i+1]):
        c += 1
    elif(ds[i]==ds[i+1]-1):
        count.append(c)
        c = 1
    else:
        valid = False
        print(0)
        break
count.append(c)

s = 1
for i in range(len(count)-1):
    s *= count[i]**count[i+1]

if(valid):
    print(int(s)%998244353)

Solution (Python):
n = int(input())
D = list(map(int, input().split()))
from collections import Counter
dic = Counter(D)
max_D = max(D)
 
num = 1
import sys
if D[0] != 0 or dic[0] != 1:
  print(0)
  sys.exit()
else:
  for i in range(1, max_D + 1):
    num *= (dic[i-1]) ** dic[i]
    num %= 998244353
print(num)

Solution (Python):
def main():
    n = int(input())
    arr = list(map(int,input().split()))
    if arr[0] != 0:
        print(0)
        return
    
    mod = 998244353
    dist = {}
    arr1 = []
    for i in arr:
        if i not in dist.keys():
            dist[i] = 1
            arr1.append(i)
        else:
            dist[i] += 1

    if dist[0] > 1:
        print(0)
        return

    arr1.sort()
    ways = 1
    for i in range(1,len(arr1)):
        ways *= pow(dist[arr1[i-1]],dist[arr1[i]],mod)
        ways = ways%mod
        if arr1[i] - arr1[i-1] != 1:
            print(0)
            return

    print(ways)
         

main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(10**5)]
MOD = 998244353

max_B = -1
ans = 1

for i in range(1, len(A)):
    if A[i]==0:
        ans = 0
    else:
        B[A[i]-1] += 1
    if A[i] > max_B:
        max_B = A[i]

if A[0] != 0:
    ans = 0 

for i in range(1, max_B):    
    if B[i] == 0:
        ans = 0 
        break
    else:
        ans = (ans * (B[i-1] ** B[i])%MOD)%MOD

print(ans)

Solution (Python):
MOD = 998244353

n = int(input())
d = list(map(int, input().split()))

stage = [0]*n
maxstage = 0
for di in d:
    stage[di] +=1
    maxstage = max(maxstage, di)

if stage[0] != 1:
    print(0)
elif d[0] != 0:
    print(0)
else:
    cnt = 1
    for i in range(1,maxstage+1):
        cnt = (cnt*stage[i-1]**stage[i])%MOD
           
    print(cnt)

Solution (Python):
INFTY = 998244353
N = int(input())
D = list(map(int,input().split()))
C = {}
dmax = 0
for i in range(N):
    d = D[i]
    dmax = max(dmax,d)
    if d not in C:
        C[d] = 0
    C[d] += 1
if D[0]!=0 or C[0]!=1:
    flag = 1
else:
    flag = 0
    for i in range(dmax+1):
        if i not in C:
            cnt = 0
            flag = 1
            break
if flag==1:
    cnt = 0
else:
    cnt = 1
    for i in range(1,dmax):
        cnt = (cnt*(C[i]**C[i+1]))%INFTY
print(cnt)

Solution (Python):
from collections import Counter
mod=998244353
N=int(input())
D=list(map(int,input().split()))
if D[0]!=0:
  print(0)
else:
  tmp=Counter(D)
  if tmp[0]!=1:
    print(0)
  else:
    ans=1
    for i in tmp.keys():
      if i==0 or i==1:
        continue
      ans*=tmp[i-1]**tmp[i]
      ans%=mod
    print(ans)