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



Sample input:
4
0 1 1 2


Sample output:
2

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import os
import math
import sys
from math import factorial
input = sys.stdin.readline


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル


def cmb(n, r, mod):
    return factorial(n) / factorial(r) / factorial(n - r)
    # if (r < 0 or r > n):
    #     return 0
    # r = min(r, n-r)
    # return g1[n] * g2[r] * g2[n-r] % mod


def main():
    N = int(input())
    d = list(map(int, input().split()))
    D = []
    d = sorted(d)

    for (k, v) in enumerate(d):
        D.append((v, k+1))

    distance = [0] * (max(d) + 1)

    for _d in D:
        distance[_d[0]] += 1

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

    if len(distance) != len([i for i in distance if i != 0]):
        print(0)
        return

    if distance[0] != 1:
        print(0)
        return

    ans = 1
    for i in range(0, len(distance)):
        if i == 0:
            ans = 1
            # print(ans)
        else:
            n = distance[i-1]
            r = distance[i]
            ans = ans * n ** r
            ans = ans % MOD
            # print(ans)

    print(ans % MOD)
    # print(*distance)
    # n = 2
    # r = 3
    # print(cmb(n+r-1, r-1, MOD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
d=sorted(list(map(int, input().split())))
num=[0]*(max(d)+1)
num_=0
count=0
j=0
for i in range(len(d)):
    if d[i]==j:
        num[j]+=1
    elif d[i]==j+1:
        num[j+1]+=1
        j+=1
    else:
        j+=1
#print(num)
ans=1
error=0
if num[0]!=1:
    error=1
for i in range(1, max(d)+1):
    #print(num[i-1]**num[i])
    ans = ans * pow(num[i-1], num[i], 998244353)
    #ans*=num[i-1]**num[i]
    if num[i]==0:
        error=1
if error==0:
    print(ans%998244353)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    Ds = [int(d) for d in input().split()]

    Ds.sort()
    if Ds.count(0) != 1:
        print(0)
        return

    i = 1
    l = 1
    r = 1
    c = []
    while i < N:
        cnt = 0
        while i < N and Ds[i] == l:
            cnt = cnt + 1
            i = i + 1
        if cnt == 0:
            print(0)
            return
        c.append((r, cnt))
        r = cnt
        l = l + 1
        
    ans = 1
    divider = 998244353
    for i, j in c:
        if j > 10:
            j1 = j//2
            j2 = j - j//2
            r1 = (i**j1)%divider
            r2 = (i**j2)%divider
            r = (r1*r2)%divider
        else:
            r = (i**j)%divider
        ans = (ans*r)%divider
    
    print(ans)

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("nikkei2019-2-qual","b",main)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
k = max(A)

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % 998244353
        x *= x % 998244353
        n //= 2

    return K * x % 998244353


R = [0] * (k + 1)
result = 1
for i in A:
    R[i] += 1

for j in range(k):
    result *= pow_k(R[j], R[j + 1])

    if result == 0:
        print(0)
        exit()

print(result % 998244353)

Submission status: Wrong Answer

Solution code:
n=int(input())
d=sorted(list(map(int, input().split())))
num=[0]*(max(d)+1)
num_=0
count=0
j=0
for i in range(len(d)):
    if d[i]==j:
        num[j]+=1
    elif d[i]==j+1:
        num[j+1]+=1
        j+=1
    else:
        j+=1
print(num)
ans=1
error=0
if num[0]!=1:
    error=1
for i in range(1, max(d)+1):
    print(num[i-1]**num[i])
    ans = ans * pow(num[i-1], num[i], 998244353) % 998244353
    #ans*=num[i-1]**num[i]
    if num[i]==0:
        error=1
if error==0:
    print(ans%998244353)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
D = list(map(int, input().split()))
l = [0] * (N-1)
top = max(D)
mod = 998244353
if D[0] != 0:
    print(0)
    exit()
for i in range(1, N):
    l[D[i]-1] += 1
# print(*l)
ans = 1
for i in range(1, top):
    if l[i] != 0:
        ans *= l[i-1] ** l[i]
    if l[i] == 0:
        print(0)
        exit()
print(ans % mod)

Submission status: Wrong Answer

Solution code:
MOD = 998244353 
N = int(input())
D = [int(x) for x in input().split()]
zero = 0 
if D[0] != 0:
    print(0)
else:
    lst = [0] * (N)
    for d in D:
        lst[d] += 1
    first0 = False
    for i in range(N):
        if (lst[i] != 0 and first0):
            print(0)
            exit()
        elif (lst[i] ==0):
            first0 = True
    ans = 1
    for i in range(N-1):
        ans *= lst[i] ** lst[i+1]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
D = [int(x) for x in input().split()]
D = sorted(D)
new_l = [0 for n in range(max(D)+1)]
ini = D[0]
for n in range(N):
    new_l[D[n]] += 1
res = new_l[0]**new_l[1]
for n in range(1,len(new_l)-1):
    res *= new_l[n]**new_l[n+1]
    res %= 998244353
print(res%998244353)

Submission status: Wrong Answer

Solution code:
N=int(input())
D=list(map(int,input().split()))
C=[0]*N
for i in range(N):
    C[D[i]]+=1
ans=1
if D[0]>0:
    print(0)
else:
    for j in range(2,max(D)+1):
        if C[j-1]==1:
            continue
        else:
            ans*=C[j-1]**C[j]
print(ans%998244353)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import os
import math
import sys
from math import factorial
input = sys.stdin.readline


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル


def cmb(n, r, mod):
    return factorial(n) / factorial(r) / factorial(n - r)
    # if (r < 0 or r > n):
    #     return 0
    # r = min(r, n-r)
    # return g1[n] * g2[r] * g2[n-r] % mod


def main():
    N = int(input())
    d = list(map(int, input().split()))
    D = []
    d = sorted(d)

    for (k, v) in enumerate(d):
        D.append((v, k+1))

    distance = [0] * (max(d) + 1)

    for _d in D:
        distance[_d[0]] += 1

    if N == 1:
        print(1)
        return

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

    if len(distance) != len([i for i in distance if i != 0]):
        print(0)
        return

    if distance[0] != 1:
        print(0)
        return

    ans = 1
    for i in range(0, len(distance)):
        if i == 0:
            ans = 1
            # print(ans)
        else:
            n = distance[i-1]
            r = distance[i]
            ans = ans * n ** r
            ans = ans % MOD
            # print(ans)

    print(ans % MOD)
    # print(*distance)
    # n = 2
    # r = 3
    # print(cmb(n+r-1, r-1, MOD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
d=sorted(list(map(int, input().split())))
num=[0]*(max(d)+1)
num_=0
count=0
j=0
for i in range(len(d)):
    if d[i]==j:
        num[j]+=1
    elif d[i]==j+1:
        num[j+1]+=1
        j+=1
    else:
        j+=1

ans=1
error=0
if num[0]!=1:
    error=1
for i in range(1, max(d)+1):
    #print(num[i-1]**num[i])
    ans = ans * pow(num[i-1], num[i], 998244353) % 998244353
    #ans*=num[i-1]**num[i]
    if num[i]==0:
        error=1
if error==0:
    print(ans%998244353)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = tuple(int(i) for i in input().split(' '))
    
counts = [0] * n
for dd in d:
    counts[dd] += 1
    
if not counts[0] == 1:
    print(0)
    exit()
 
result = 1;
for i in range(1, n-1):
    result *= pow(counts[i], counts[i+1])
    
print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())
D = list(map(int, input().split()))
D.sort()
# print(D)
 
def calc(N, D):
  counts = [0]
  preNum = 0
  for i in D:
    if i == preNum:
      counts[-1] += 1
    elif i == preNum + 1:
      counts.append(1)
    else:
      return 0
    preNum = i
  result = 1
  for i in range(len(counts)-1):
    result = result * pow(counts[i], counts[i+1])
  return result%998244353
 
print(calc(N, D))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [int(x) for x in input().split()]
s.sort()
deep,a,b,c = 0,1,0,1
for i in range(n):
  if s[i] == deep:
    b += 1
  elif i == n:
    c *= a ** b
  elif s[i] == deep + 1:
    c *= a ** b
    a = b
    b = 1
    deep += 1
  else:
    c = 0
    break
    
  if i == n-1:
    if s[i] == deep:
      c *= a ** b
      c = c % 998244353
    elif s[i] == deep + 1:
      c *= a ** b
      c = c % 998244353
    else:
      c = 0
      break

if s.count(0) == 1:
  print(c)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

if D[0] != 0:
    print(0)
elif sum(D == 0) != 1:
    print(0)
elif sum(np.diff(np.array(list(set(D)))) != 1):
    print(0)
else:
    print(np.prod(D[1:]) % 998244353)

Submission status: Wrong Answer

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

if n==1:
	if d[0]==0:
		print(1)
		exit()
	else:
		print(0)
		exit()
elif n==2:
	if d==[0,1]:
		print(1)
		exit()
	else:
		print(0)
		exit()
if d[0]!=0 or d[1]!=1:
	print(0)
	exit()
for i in range(n-1):
	if d[i+1]>d[i]+1:
		print(0)
		exit()
p=[]
cnt=1
for i in range(1,n-1):
	if d[i]==0:
		print(0)
		exit()
	if d[i]==d[i+1]:
		cnt+=1
	elif d[i+1]==d[i]+1:
		p.append(cnt)
		cnt=1
p.append(cnt)
ans=1
for i in range(len(p)-1):
	ans*=pow(p[i],p[i+1],mod)
	ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# from operator import mul
# from functools import reduce
# import itertools

# def combinations_count(n, r):
#     r = min(r, n - r)
#     numer = reduce(mul, range(n, n - r, -1), 1)
#     denom = reduce(mul, range(1, r + 1), 1)
#     return numer // denom

# def combinations_with_replacement_count(n, r):
#     return combinations_count(n + r - 1, r)

N = int(input())
D_list = list(map(int, input().split()))
 
pattern_dic = {}
zero_flag = 0
ans = 1
if D_list[0] != 0:
    print(0)
else:
    for i in range(1, N):
        pattern_dic[D_list[i]] = pattern_dic.get(D_list[i], 0) + 1
    if 1 in pattern_dic:
        before_num = pattern_dic[1]
        for j in range(2, max(pattern_dic.keys()) + 1):
            if j in pattern_dic:
                ans *= before_num ** pattern_dic[j] % 998244353
                before_num = pattern_dic[j]
            else:
                zero_flag = 1
                break
    else:
        zero_flag = 1
 
    if zero_flag == 1:
        print(0)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()] 
if a[0]!=0:
    print (0%998244353)
else:
    a = Counter(a)
    ans = 1
    for i in range(1,len(a)-1): 
        ans*=a[i]**a[i+1]
    print(ans%998244353)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
mod = 998244353
b=a.pop(0)
if b!=0:print(0);exit()
import collections
d=collections.Counter(a)
e=[[i,j] for i,j in d.items()]
e.sort()
ans=1
d1=[i[0] for i in e]
d2=[i[1] for i in e]
for i,I,j,J in zip(d1,d1[1:],d2,d2[1:]):
    if i+1!=I:
        print(0)
        exit()
    ans*=j**J%mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
MOD = 998244353

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

c = Counter(D)
if c[0] != 1:
    print(0)
    exit(0)
d = max(c)
ans = 1
base = 1
for i in range(1, d+1):
    if c[i] == 0:
        print(0)
        exit(0)
    ans *= pow(base, c[i], MOD)
    ans = ans % MOD
    base = c[i]

print(ans)

Submission status: Wrong Answer

Solution code:
def modpow(a, n, mod):
    bi = format(n, 'b')
    res = 1
    for i in range(len(bi)):
        res = (res * res) % mod
        if bi[i] == '1':
            res = (res * a) % mod
    return res

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

L = [0] * (max(D) + 1)
for d in D:
    L[d] += 1

if (L[0] != 1) & (D[0] == 0):
    ans = 0
else:
    ans = 1
    for i in range(len(L)-1):
        ans *= modpow(L[i], L[i+1], mod)
        ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
# 指定された距離で何個の木を作成することができるかを計算する
import bisect
import itertools
N = int(input())
D = list(map(int, input().split()))
node_dis = [1] # 距離iのノードの個数をi番目の要素として格納したリスト
flag_none = False

# 頂点１から深さは決まっている.深さni毎に前のni-1のノードから重複を許してc_ni個選んでノードに繋げばよい
if not D[0] == 0:
    print(0)
    flag_none = True

else:
    D.sort()  # 昇順でソート
    for i in range(1,N):
        if i == 1 and bisect.bisect_left(D,1) >= 2:  # 0が２つ以上ある場合
            print(0)
            flag_none = True
            break
        else:
            if i ==1:
                del D[0]
            index = bisect.bisect_left(D,i+1)
            new_num = index 
            node_dis.append(new_num)
            del D[:index]
            if index==0: 
                if not D == []:
                    print(0)
                    flag_none = True
                break
if flag_none == False:
    sum = 1
    for (ind, di) in enumerate(node_dis): 
        if ind > 0:
            sum *= node_dis[ind-1] ** di
    print(sum)

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())

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

D.sort()
D_max = D[-1]
count = 0
a = 1

if D[0]!=0:
    print(0)
else:
    for i in range(N-1):
        if D[i+1]-D[i] > 1: 
            count += 1
    if count > 0:
        print(0)
    else:
        l = collections.Counter(D)
        for i in range(1,D_max+1):
            a = a*(l[i-1]**l[i])
        print(a)

Submission status: Wrong Answer

Solution code:
from collections import Counter

mod = 998244353

N, D1, *D = map(int, open(0).read().split())

if D1 != 0:
    print(0)
    quit()

C = Counter(D)

ans = 1
for i in range(1, max(C.keys(), default=0) + 1):
    if C[i] == 0:
        ans = 0
        break
    ans *= pow(i, C[i], mod)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import accumulate

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

if not D[0] == 0:
    print("0")
elif D.count(0) >= 2:
    print("0")
else:
    for i in range(max(D)):
        if not i in D:
            print("0")
            exit()
    D.sort()
    anss = [D.index(i+1) - D.index(i) for i in range(1,max(D))]
    anss.append(N-sum(anss)-1)
    ans = [(i+1)**anss[i] for i in range(len(anss))]
    ans = np.prod(ans, axis = 0)
    print(ans%998244353)

Submission status: Wrong Answer

Solution code:
def modpow(a, n, mod):
    bi = format(n, 'b')
    res = 1
    for i in range(len(bi)):
        res = (res * res) % mod
        if bi[i] == '1':
            res = (res * a) % mod
    return res

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

L = [0] * (max(D) + 1)
for d in D:
    L[d] += 1

L = [1, 100000, 10000]    
if (L[0] != 1) & (D[0] == 0):
    ans = 0
else:
    ans = 1
    for i in range(len(L)-1):
        ans *= modpow(L[i], L[i+1], mod)
        ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

n = int(input())
d = list(map(int,sys.stdin.readline().split()))
d = sorted(Counter(d).items(),key=lambda x:x[0])
cnt = d[0][1]

for i in range(len(d)):
    if i != d[i][0]:
        print('0')
        break
    elif i != 0:
        cnt *= i**d[i][1]
else:
    print(cnt%998244353)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
n = int(input())
d = list( map(int, input().split()) )
MOD = 998244353

c = Counter(d)

def count(c, iter):
    if c[0] != 1 or d[1] != 0:
        return 0

    res = 1
    for i in range(2, iter+2):
        for _ in range(c[i]):
            res *= c[i-1]%MOD
        res %= MOD
    return res%MOD

res = count(c, max(d))
print(res)

Submission status: Wrong Answer

Solution code:
N=int(input())
d=list(map(int,input().split()))
count=1
if d[0]!=0:
    count=0
for i in range(N):
    count *= ((i+1) ** d.count(i+1))%99844353

print(count%99844353)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()] 
if a[0]!=0:
    print ("0")
else:
    a = Counter(a)
    ans = 1
    for i in range(1,len(a)-1): 
        ans*=a[i]**a[i+1]
    print(ans%998244353)

Submission status: Wrong Answer

Solution code:
import collections
 
n = int(input())
d = list(map(int,input().split()))
MOD = 998244353
  
#同じ長さの位置に何個頂点があるか
cnt = dict(collections.Counter(d))
#print(cnt)

try:
  if cnt[0]==1:
    ans = 1
    for i in range(len(dict(cnt))-1):
      if i not in cnt:
        print(0)
        exit()
      val_1 = cnt[i]
      val_2 = cnt[i+1]
      ans *= (val_1**val_2)%MOD
 
    print(ans%MOD)
  else:
    print(0)
except KeyError:
  print(0)
#なんでACにならないのか・・・
#例外処理が足りてないのか....
#0が複数個orなしのときは書いた
#

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
D = np.array(list(map(int, input().strip().split())))

if D[0] == 0:
    count = [0] * len(D)
    max_d = 0
    for d in D:
        count[d] += 1
        if d > max_d:
            max_d = d

    ans = 1
    for i in range(2,max_d+1):
        if count[i] <= 0:
            ans = 0
            break
        ans *= count[i-1]**count[i]

    print(ans%998244353)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
mod = 998244353

N = int(input())
D = [int(x) for x in input().split()]

dep = max(D)
dict = [0]*(dep+1)

for d in D:
    dict[d]+=1
if(dict[0]!=1 and D[0]!=0):
    ans = 0
else:
    ans = 1
    for de in range(1,dep+1):
        ans *= (dict[de-1]**dict[de])%mod
        ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = list(map(int,input().split()))
db = [0] * n
MOD = 998244353

#距離iの頂点の数をdb[i]に保存
for i in range(n):
    db[d[i]] += 1

#末尾に連続する0を削除
if (db[n-1] == 0):
    l = n-1
    for i in range(1,n):
        tmp = db[n-i]
        if (tmp == 0) : l = n-i 
        else : break
    
    del db[l:n]


if (d[0] != 0)|(db[0] != 1):
    print(0)
    exit()
if (len(db) <= 2):
    print(len(db)-1)
    exit()

db.append(1)
ans = 1

for i in range(len(db)-1):
    tmp = (db[i]**db[i+1]) % MOD
    ans *= tmp

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
DIVISOR = 998244353
sys.setrecursionlimit(10001)

def Counting_of_trees(dist):
    if len(dist) == 1:
        if dist[0] == 0:
            return 1
        else:
            return 0

    arg = dist.argmax()
    dist_cuted = np.delete(dist, arg )

    cnt = np.count_nonzero(dist_cuted == dist.max() - 1)*Counting_of_trees(dist_cuted)
    return cnt

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

#print( Counting_of_trees(D) )
print( Counting_of_trees(D) % DIVISOR)

Submission status: Wrong Answer

Solution code:
N=int(input())
d=list(map(int,input().split()))
count=1
if d[0]!=0:
    count=0
for i in range(N):
    count *= (i+1) ** d.count(i+1)

print(count%99844353)

Submission status: Wrong Answer

Solution code:
N = int(input())
D = [int(x) for x in input().split()]
D = sorted(D)
new_l = [0 for n in range(N)]
ini = D[0]
for n in range(N):
    new_l[D[n]] += 1
res = new_l[0]**new_l[1]
for n in range(1,len(new_l)-1):
    res *= new_l[n]**new_l[n+1]
    res %= 998244353
print(res%998244353)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


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

    C = [0] * (max(D) + 1)
    for d in D:
        C[d] += 1
    # print(C)
    
    ans = 1
    if C[0] == 0:
        print(0)
        return
    for i in range(len(C) -1):
        ans *= C[i] ** C[i+1]
    
    print(ans % 998244353)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import os
import math
import sys
from math import factorial
input = sys.stdin.readline


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル


def cmb(n, r, mod):
    return factorial(n) / factorial(r) / factorial(n - r)
    # if (r < 0 or r > n):
    #     return 0
    # r = min(r, n-r)
    # return g1[n] * g2[r] * g2[n-r] % mod


def main():
    N = int(input())
    d = list(map(int, input().split()))
    D = []
    d = sorted(d)

    for (k, v) in enumerate(d):
        D.append((v, k+1))

    distance = [0] * (max(d) + 1)

    for _d in D:
        distance[_d[0]] += 1

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

    if len(distance) != len([i for i in distance if i != 0]):
        print(0)
        return

    ans = 1
    for i in range(0, len(distance)):
        if i == 0:
            ans = 1
            # print(ans)
        else:
            n = distance[i-1]
            r = distance[i]
            ans = ans * n ** r
            # print(ans)

    print(ans % MOD)
    # print(*distance)
    # n = 2
    # r = 3
    # print(cmb(n+r-1, r-1, MOD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
li = list(map(int,input().split()))
count_li = collections.Counter(li)
DIV = 998244353

a_list = count_li.most_common()
a_list.sort()
ans = 1

if li[0] != 0:
    print(0)
else:
    for i in range(len(a_list) - 1):
        ans *= a_list[i][1] ** a_list[i + 1][1] % DIV
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int, input().split()))

div_num = 998244353
result = 1
ct_l = []

for i in range(max(l)+1):
    ct_l.append(0)

for item in l:
    ct_l[item] += 1

print(ct_l)
prev_v = -1
curr_v = -1
e = n-1

for i, item in enumerate(ct_l):
    if i == 2:
        break
    if i == 0 and item == 1:
        pass
    else:
        e -= item
    if i == 1:
        prev_v = item

for i, item in enumerate(ct_l[2:]):
    #print(prev_v, item, e, result)
    e -= item
    if item == 0:
        break
    curr_v = item
    result *= prev_v**curr_v
    result %= div_num
    prev_v = curr_v
    #print(prev_v, curr_v, result)

if e < 0 or e > 0 or l[0] > 0:
    print(0)
elif n == l[1]:
    print(1)
else:
    print(result)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
D=list(map(int,input().split()))
M=max(D)
l=[0]*(M+1)
for i in D:
    l[i]+=1
if l[0]==1:
    a=1
    for i in range(M):
        a*=pow(l[i],l[i+1],998244353)
    a%=998244353
    print(a)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()] 
if a[0]!=0:
    print ("0")
else:
    a = Counter(a)
    ans = 1
    for i in range(1,len(a)):   
        print(a[i])
        ans*=a[i]**a[i+1]
    print(ans%998244353)

Submission status: Wrong Answer

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

D.sort()
count = [0]*(D[-1]+1)
ans = 1

if D[0] != 0 or D[1] == 0:
    print(0)
    exit()
count[0] = 1
for i in range(N-1):
    if D[i+1]-1 > D[i]:
        print(0)
        exit()
    count[D[i+1]] += 1

for i in range(1,D[-1]+1):
    ans *= count[i-1]**count[i]
    ans %= 998244353
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


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

    C = [0] * (max(D) + 1)
    for d in D:
        C[d] += 1
    # print(C)
    
    ans = 1
    for i in range(len(C) -1):
        ans *= C[i] ** C[i+1]
    
    print(ans % 998244353)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
d = list(map(int,input().split()))
li = []
d.sort()
cnt = 0
ans = 1
b = 0
if d[0] != 0:
  print("0")
elif d[1] == 0:
  print("0")
elif d[-1] > n-1:
  print("0")
else:
  for i in range(1,n-1):
    if d[i] == d[i+1]:
      if d[i] != len(li)+1:
        b = 1
      cnt += 1
    else:
      if d[i] != len(li)+1:
        b = 1
      cnt += 1
      li.append(cnt)
      cnt = 0
    if i == n-2:
      if d[n-2] == d[n-1]:
        cnt += 1
        li.append(cnt)
      else:
        li.append(1)
  if b == 0:
    for i in range(len(li)-1):
      k=1
      for l in range(li[i+1]):
        k = k*li[i]
        if k > 998244353:
          k = k%998244353
      ans = (ans*(k%998244353)%998244353)
    print(ans)
  else:
    print("0")

Submission status: Wrong Answer

Solution code:
MOD = 998244353 
N = int(input())
D = [int(x) for x in input().split()]
lst = [0] * (N)
for d in D:
    lst[d] += 1
if (lst[0] == 1):
    f = 0
    for i in range(N):
        if (lst[i] == 0 and f == 0):
            f = 1
        if (f and lst[i] != 0):
            print(0)
            exit()
    ans = 1
    for i in range(N-1):
        ans *= pow(lst[i], lst[i+1], MOD)
    print(ans)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def main():
    MOD = 998244353
    N = int(input())
    D = [int(i) for i in input().split()]
    if D[0] != 0:
        return print(0)
    from collections import Counter
    c = Counter(D)
    ans = 1
    for k, v in c.items():
        if k == 0 or k == 1:
            continue
        elif v == 0:
            return print(0)
        else:
            if c[k-1] <= v:
                ans *= c[k-1]**v
            else:
                ans *= c[k-1]
            ans = int(ans) % MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
Ds = list(map(int, input().split()))
Dsi = [[Ds[i], i+1] for i in range(n)]
length = max(Ds) + 1
Pts = list()

Dsi = sorted(Dsi)
# print(Dsi, 'Dsi', 'Ds', Ds)


start = 0
Iss = list()
for i in range(length):
    Is = list()

    #距離がiであるようなヤツを探す
    for j in range(start, length+1):

        # print(i, j)
        if Dsi[j][0] == i:
            Is.append(Dsi[j][1])
        else:
            start = j-1
            break

    
    Iss.append(Is)

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)


for i in range(len(Iss)):
    if i == 0:
        Pts.append(math.factorial(len(Iss[i])))
    else:
        m = len(Iss[i])
        n = len(Iss[i-1])
        if m < n or m <= 1 or n <= 1:
            Pts.append(m**n * Pts[i-1])

            #print(i, Pts[i], 'bbb', m, n)
        else:
            st_p = permutations_count(m - 1, n-1) 
            r_p  = math.factorial(m) * math.factorial(n)

            Pts.append(st_p * r_p * Pts[i-1])
            
            #print(i, Pts[i], 'aaa', m, n)
print(Pts[-1])
print('iss', Iss)

Submission status: Wrong Answer

Solution code:
import operator as op
from functools import reduce

n = int(input())

ds = map(int, input().split(' '))
ds = list(ds)
modulus = 998244353


def prod(nums, start_value=1):
    result = start_value
    for num in nums:
        result *= num

    return result


# def ncr(n, r):
#     r = min(r, n-r)
#     numer = reduce(op.mul, range(n, n-r, -1), 1)
#     denom = reduce(op.mul, range(1, r+1), 1)
#     return numer / denom


def f(q, p):
    return q ** p
    # if q == 1:
    #     return 1
    # result = 0
    # for k in range(0, p+1):
    #     result += ncr(p, p-k) * f(q-1, p-k)
    # return result


q = ds.count(0)
if(q != 1):
    print(0)
    exit()

result = 1
for i in range(0, max(ds) + 1):
    if not i in ds:
        print(0)
        exit()

    p = ds.count(i+1)
    result *= f(q, p) % modulus
    q = p


print(int(result))

Submission status: Wrong Answer

Solution code:
import collections
  
N = int(input())
D = list(map(int, input().split()))
ans = 1
e = 0
  
l = collections.Counter(D)  
 
for i in range(N-2):
  if l[i] != 0:
      ans *= l[i] ** l[i+1]
 
for i in range(N-1):
  if l[i] == 0 and l[i+1] != 0:
    e = 1
     
if D.count(0) != 1 or e == 1:
  print(0)
else:
  print(ans % 998244353)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int, input().split()))
box = [0 for x in range(max(li)+1)]
for i in li:
    box[i] += 1
count = 1

if len(box) > 2:
    for i in range(1, len(box)-1):
        count *= box[i] ** box[i+1]
        count %= 998244353
else:
    count = 1
    
if box[0] != 1:
    count = 0

print(count % 998244353)

Submission status: Wrong Answer

Solution code:
import sys
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 998244353
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()
a.sort()
num = a[-1]
aset = [0 for i in range(num+1)]

for i in a:
  aset[i] += 1
#print(aset)
if aset[0] == 1:
  ans = 1
  for i in range(1,num+1):
    ans *= (aset[i-1]**aset[i]) %mod
    #print(aset[i-1], aset[i])
  print(ans %mod)

else:
  print(0)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import Counter
N = int(stdin.readline().rstrip())
D = [int(x) for x in stdin.readline().rstrip().split()]
mod = 998244353
ans = 1
if N == 1 and D[0] == 0:
    print(1)
elif len(set(D))==1:
    print(0)
elif D.count(0) != 1:
    print(0)
else:
    tmp = 1
    cnt = Counter(D)
    #print(cnt)
    flag = True
    for i in range(1,max(D)+1):
        #print(cnt[i],tmp)
        if i != 1 and cnt[i] != tmp:
            flag = False
        c = (tmp**cnt[i]) % mod
        ans *= c % mod
        tmp = cnt[i]
        ans = ans % mod
    if flag:
        print(1)
    else:
        print(ans % mod)