Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import copy
from collections import deque


H, W = map(int, input().split())
past_map = [list(input()) for _ in range(H)]


def make_new_map(p_map):

    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    n_map = copy.deepcopy(p_map)
    reached = [[False for _ in range(W)] for _ in range(H)]

    for sh in range(H):
        for sw in range(W):
            if (reached[sh][sw] is False) and (p_map[sh][sw] == '#'):
                # start bfs
                togo = deque()
                togo.append((sh, sw))
                reached[sh][sw] = True
                while len(togo):
                    h, w = togo[0][0], togo[0][1]
                    togo.popleft()
                    for d in range(4):
                        nh, nw = h + dy[d], w + dx[d]
                        if nh < 0 or nw < 0 or nh >= H or nw >= W:
                            continue
                        if n_map[nh][nw] == '.':
                            n_map[nh][nw] = '#'
                        if reached[nh][nw] is True:
                            continue
                        if p_map[nh][nw] == '.':
                            continue
                        togo.append((nh, nw))
                        reached[nh][nw] = True
    return n_map


count = 0
next_map = make_new_map(past_map)
while past_map != next_map:
    count += 1
    past_map = copy.deepcopy(next_map)
    next_map = make_new_map(past_map)
print(count)


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

checked = [[False for _ in range(W)] for _ in range(H)]

que = deque()
flag = False
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            que.append((i, j))
            checked[i][j] = True
        else:
            flag = True

if flag is False:
    print('0')
    exit()

n_que = deque()
step = 0
while len(que):

    h, w = que[0][0], que[0][1]
    que.popleft()
    for d in range(4):
        nh, nw = h + dy[d], w + dx[d]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if checked[nh][nw] is True:
            continue
        n_que.append((nh, nw))
        checked[nh][nw] = True

    if len(que) == 0:
        if len(n_que) == 0:
            print(step)
            exit()
        que = n_que
        n_que = deque()
        step += 1
### BUGGY CODE ###

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second
# print (left, right)

left_lst = [1] * (left + 1) 
for i in range(1, left + 1):
    left_lst[i] = (left_lst[i - 1] * (left + 1 - i)) // i
# print (left_lst)

right_lst = [1] * (right + 1)
for i in range(1, right + 1):
    right_lst[i] = (right_lst[i - 1] * (right + 1 - i)) // i
# print (right_lst)


def calc(i): #1を含めてトータルi個選ぶ
    if i == 1:
        return 1
    count = 0
    #左側からl個、右側からr個選ぶ
    start = max((i - 1) - right, 0) #左側から最低限選ばないといけない個数
    for l in range(start, min(i, left + 1)):
        count += left_lst[l] * right_lst[i - 1 - l]
    return count

N = n + 1
tmp = 1
for i in range(1, n + 2):
    tmp = (tmp * (N + 1 - i))//i
    if left + right < i - 1:
        print (tmp % MOD)
        continue
    print ((tmp - calc(i)) % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n

# O(N)
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second

U = 10 ** 5 + 1
def power_mod(a, n):
    if n == 0:
        return 1
    x = power_mod(a//2)

def make_fact(fact, fact_inv):
    for i in range(1, U + 1):
        fact[i] = (fact[i - 1] * i) % MOD
    fact_inv[U] = pow(fact[U], MOD - 2, MOD)
    for i in range(U, 0, -1):
        fact_inv[i - 1] = (fact_inv[i] * i) % MOD

def comb(n, k):
    if k < 0 or n < k:
        return 0
    x = fact[n]
    x *= fact_inv[k]
    x %= MOD
    x *= fact_inv[n - k]
    x %= MOD
    return x

fact = [1] * (U + 1)
fact_inv = [1] * (U + 1)
make_fact(fact, fact_inv)

for i in range(1, n + 2):
    ans = comb(n + 1, i) - comb(left + right, i - 1)
    print (ans % MOD)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]
dp = glist(n1+n2+n3+1, n2+n3+1, n3+1)
dp[0][0][0] = 0
def sub(i1,i2,i3):
    if dp[i1][i2][i3] is not None:
        return dp[i1][i2][i3]
    ans = n
    if i1>0:
        ans += i1 * sub(i1-1,i2,i3)
    if i2>0:
        ans += i2 * sub(i1+1,i2-1,i3)
    if i3>0:
        ans += i3 * sub(i1,i2+1,i3-1)
    ans = ans/(i1+i2+i3)
    dp[i1][i2][i3] = ans
    return ans
print(sub(n1,n2,n3))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]

count = 0
S = sum(a)
sub = glist(n1+n2+n3+1,n2+n3+1,n3+1)
sub[0][0][0] = 0
#     for i1 in range(min(n+1, s+1)):
#         for i2 in range(min(n+1, (s-i1)//2+1)):
for i3 in range(n3+1):
    for i2 in range(n2+n3+1-i3):
        for i1 in range(n1+n2+n3 - (i2+i3) + 1):
            if i1==i2==i3==0 or i1+i2+i3>n:
                continue
#             print(i1,i2,i3)
            ans = n
            p = 0
            if i1>0:
                ans += i1 * sub[i1-1][i2][i3]
                p += i1
            if i2>0:
                ans += i2 * sub[i1+1][i2-1][i3]
                p += i2
            if i3>0:
                ans += i3 * sub[i1][i2+1][i3-1]
                p += i3
            ans = ans/p
            sub[i1][i2][i3] = ans
print(sub[n1][n2][n3])
### BUGGY CODE ###

# Problem A - Range Flip Find Route

# input
h, w = map(int, input().split())
s_board = [['.']*w for i in range(h)]
c_board = [[100000]*w for i in range(h)]
for i in range(h):
    w_line = list(input())
    for j in range(w):
        s_board[i][j] = w_line[j]

# initialization
visit_queue = []

# count step
visit_queue.append([0, 0])
c_board[0][0] = 0
while len(visit_queue)>0:
    q = visit_queue.pop(0)
    r = q[0]
    c = q[1]
    # right
    if c+1<w:
        if s_board[r][c]=='.' and s_board[r][c+1]=='#':
            c_board[r][c+1] = min(c_board[r][c+1], c_board[r][c]+1)
        else:
            c_board[r][c+1] = min(c_board[r][c+1], c_board[r][c])
        visit_queue.append([r, c+1])
    # down
    if r+1<h:
        if s_board[r][c]=='.' and s_board[r+1][c]=='#':
            c_board[r+1][c] = min(c_board[r+1][c], c_board[r][c]+1)
        else:
            c_board[r+1][c] = min(c_board[r+1][c], c_board[r][c])
        visit_queue.append([r+1, c])

# start adjust
if s_board[0][0]=='#':
    c_board[h-1][w-1] += 1

# output
print(c_board[h-1][w-1])


### FIXED CODE ###

# Problem A - Range Flip Find Route

# input
h, w = map(int, input().split())
s_board = [['']*w for i in range(h)]
for i in range(h):
    s = list(input())
    for j in range(w):
        s_board[i][j] = s[j]

# initialization
INF = 10**5
dp = [[INF]*w for i in range(h)]
if s_board[0][0]=='#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

# count
for i in range(h):
    for j in range(w):
        # skip
        if i==0 and j==0:
            continue

        # left
        if j-1>=0:
            if s_board[i][j]=='#' and s_board[i][j-1]=='.':
                dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
            else:
                dp[i][j] = min(dp[i][j], dp[i][j-1])

        # up
        if i-1>=0:
            if s_board[i][j]=='#' and s_board[i-1][j]=='.':
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
            else:
                dp[i][j] = min(dp[i][j], dp[i-1][j])

# output
print(dp[-1][-1])
### BUGGY CODE ###

a = int(input())
b = input().split()

for i in range(0,len(b)):
    b[i]=int(b[i])



res=1
state=1
length = len(b)
for i in range(0,length):
    res*=b[i]
    if res==0:
        print(res)
        state=0
        break

if state==1:
    if res>1000000000000000000:
        print("-1")
    else:
        print(res)

### FIXED CODE ###

a = int(input())
b = input().split()

for i in range(0,len(b)):
    b[i]=int(b[i])



state=1
for x in b:
    if x==0:
        state=0
        print("0")
        break

res=1
if state==1:
    for x in b:
        res*=x
        if res>1000000000000000000:
            print("-1")
            state=0
            break

if state==1:
    print(res)
### BUGGY CODE ###

from numba import jit

N,M=map(int,input().split())
A=list(map(int,input().split()))

need =(2,5,5,4,5,6,3,7,6)

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
if 1 in A and 4 in A:
  del A[A.index(4)]
if 6 in A and 7 in A:
  del A[A.index(6)] 
if 7 in A and 9 in A:
  del A[A.index(9)] 
if 1 in A and 6 in A:
  del A[A.index(6)] 
if 1 in A and 9 in A:
  del A[A.index(9)] 
  
A = tuple(A)
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

@jit
def take_max():
  return max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = take_max()
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))

if N % 2 == 0:
  if 1 in A:
    print(int('1'*(N//2)))
    exit()

need =(2,5,5,4,5,6,3,7,6)

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
if 1 in A and 4 in A:
  del A[A.index(4)]
if 6 in A and 7 in A:
  del A[A.index(6)] 
if 7 in A and 9 in A:
  del A[A.index(9)] 
if 1 in A and 6 in A:
  del A[A.index(6)] 
if 1 in A and 9 in A:
  del A[A.index(9)] 
  
A = tuple(A)
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

def take_max():
  return max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = take_max()
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])
### BUGGY CODE ###

p=int(input())
A=list(map(int,input().split()))

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
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

  
def power_func(x,y,z):
  bi=str(format(y,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %z
    if bi[i]=="1":
      res=(res*x) %z
  return res
C=[]
for i in range(p):
  C.append(comb(p-1,i,p))


B=[0]*p
if A[0]==0:
  for i in range(p):
    if A[i]==1:
      for j in range(p):
        B[j]=B[j]+(-1)**(j+1)*C[j]*(i**(p-j-1)%p)
        #B[j]=B[j]+(-1)**(j+1)*C[j]*power_func(i,p-j-1,p)
      B[0]=B[0]+1
else:
  B[0]=1
  for i in range(1,p):
    if A[i]==0:
      for j in range(p):
        B[j]=B[j]-(-1)**(j+1)*C[j]*(i**(p-j-1)%p)
        #B[j]=B[j]-(-1)**(j+1)*C[j]*power_func(i,p-j-1,p)
      B[0]=B[0]-1
for i in range(p-1):
  print(B[i]%p,end=" ")
print(B[-1]%p)

### FIXED CODE ###

p=int(input())
A=list(map(int,input().split()))
cmb=[0]*p
cmb[0]=1
for i in range(1,p):
  cmb[i]=cmb[i-1]*(p-i)*pow(i,p-2,p)%p
ans=[0]*p
for i in range(p):
  if A[i]==1:
    b=1
    ans[0]=ans[0]+1
    for j in range(p):
      ans[p-j-1]=(ans[p-j-1]-cmb[j]*b)%p
      b=b*(-i)%p
for i in range(p-1):
  print(ans[i],end=" ")
print(ans[p-1])
### BUGGY CODE ###

import sys
n,k=map(int,input().split())
if n==0 or n%k==0:
    print(0)
    sys.exit()
tmp=abs(n-k)
while tmp<n:
    n=tmp
    tmp=abs(n-k)
print(n)

### FIXED CODE ###

import sys
n,k=map(int,input().split())
if n==0 or n%k==0:
    print(0)
    sys.exit()
n=n%k
tmp=abs(n-k)
while tmp<n:
    n=tmp
    tmp=abs(n-k)
print(n)
### BUGGY CODE ###

from math import factorial

Mod = 10**9 + 7


def Cmb(n, k):
    return factorial(n) // (factorial(n - k) * factorial(k)) % Mod


n, m, k = list(map(int, input().split()))

ans = 0

for i in range(1, n + 1):
    ans += i * (n - i) * m**2 % Mod

for i in range(1, m + 1):
    ans += i * (m - i) * n**2 % Mod

ans *= Cmb(n * m - 2, k - 2)
ans %= Mod

print(ans)


### FIXED CODE ###

import sys
from math import factorial

input = sys.stdin.readline

Mod = 10**9 + 7


def Cmb(n, k):
    return factorial(n) // (factorial(n - k) * factorial(k)) % Mod


n, m, k = list(map(int, input().split()))

ans = 0

for i in range(1, n + 1):
    ans += i * (n - i) * m**2 % Mod

for i in range(1, m + 1):
    ans += i * (m - i) * n**2 % Mod

ans *= Cmb(n * m - 2, k - 2)
ans %= Mod

print(ans)
### BUGGY CODE ###

def fact(i):
  val =1
  for j in range(2,i+1):
    val *= j
  return val
inf = input().split()
N = int(inf[0])
K = int(inf[1])
M = N-K
for i in range(1,K+1):
  red = fact(M+1)//(fact(i)*fact(M+1-i))
  blue = fact(K-1)//(fact(i-1)*fact(K-i))
  print(red*blue%(10**9+7))


### FIXED CODE ###

from operator import mul
from functools import reduce
 
def cmb(n,r):
    r = min(n-r,r)
    if r==0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

inf = input().split()
N = int(inf[0])
K = int(inf[1])
M = N-K
for i in range(1,K+1):
  if M+1<i:
    red = 0
  else:
    red = cmb(M+1,i)
  blue = cmb(K-1,i-1)
  print(red*blue%(10**9+7))
### BUGGY CODE ###

import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.depth = pow(2, n.bit_length())

    def add(self, i, x=1):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    # Return sum for [l, r)
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)

    # Return the minimum i that satisfies a_0 + a_1 + ... + a_i >= x
    def lower_bound(self, x):
        if x <= 0:
            return 0
        i = 0
        k = pow(2, self.depth)
        while k:
            if i + k < self.n and self.data[i + k] < x:
                x -= self.data[i + k]
                i += k
            k >>= 1
        return i


def main():
    N, *P = map(int, read().split())

    index = [0] * (N + 1)
    for i, p in enumerate(P):
        index[p] = i

    bit = BIT(N)

    ans = 0
    for n in range(N, 0, -1):
        i = index[n]
        bit.add(i)
        x = bit.get_sum(i)

        left1 = left2 = -1
        right1 = right2 = N
        if x - 2 > 0:
            left2 = bit.lower_bound(x - 2)
        if x - 1 > 0:
            left1 = bit.lower_bound(x - 1)
        if x + 1 <= N - n + 1:
            right1 = bit.lower_bound(x + 1)
        if x + 2 <= N - n + 1:
            right2 = bit.lower_bound(x + 2)

        ans += ((left1 - left2) * (right1 - i) + (right2 - right1) * (i - left1)) * n


    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *P = map(int, read().split())

    idx = [0] * (N + 1)
    for i, p in enumerate(P):
        idx[p] = i

    left = list(range(-1, N)) + [-1]
    right = list(range(1, N + 1)) + [N, N]

    ans = 0
    for n in range(1, N + 1):
        i = idx[n]
        l1 = left[i]
        l2 = left[l1]
        r1 = right[i]
        r2 = right[r1]

        ans += n * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))

        left[r1] = l1
        right[l1] = r1

    print(ans)
    return


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys

def main():
    _ = int(input())
    A = list(map(int, sys.stdin.readlines()))
    
    arr = [A[0]]
    for a in A[1:]:
        if a <= arr[-1]:
            arr.append(a)
        else:
            for i in range(len(arr)):
                if a > arr[i]:
                    arr[i] = a
                    break
    print(len(arr))
    
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
import bisect
from collections import deque

def main():
    _ = int(input())
    A = list(map(int, sys.stdin.readlines()))
    
    arr = deque()
    arr.append(A[0])
    for a in A[1:]:
        if a <= arr[0]:
            arr.appendleft(a)
        else:
            insert_index = bisect.bisect_left(arr, a)
            update = max(0, insert_index-1)
            arr[update] = a
    print(len(arr))
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

n = int(input())
l = [int(x) for x in input().split()]
m = sorted((i for i in set(l) if l.count(i) > 1), reverse=True)
if len(m) > 0:
  x = m[0]
  if l.count(x) > 3:
    print(x*x)
  elif len(m) > 1:
    y = m[1]
    print(x*y)
  else:
    print(0)
else:
  print(0)

### FIXED CODE ###

n = int(input())
l = sorted((int(x) for x in input().split()), reverse = True)
a = []
t = None
for x in l:
  if t == x:
    t = None
    a.append(x)
    if len(a) > 1:
      break
  else:
    t = x
print(a[0]*a[1] if len(a) > 1 else 0)
### BUGGY CODE ###

import sys
import math
input = sys.stdin.readline


def main():
    sc = Scan()
    N = sc.intarr()[0]
    S = sc.strarr()[0]

    array = []
    for i in range(N):
        for j in range(i+1, N):
            Marray = []
            for m in range(j+1, N):
                Marray.append(S[m])
                Marray = list(set(Marray))
                if len(Marray) == 10:
                    break
                num = S[i] + S[j] + S[m]
                array.append(num)
    array = set(array)
    print(len(array))


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


main()


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline


def main():
    sc = Scan()
    _ = sc.intarr()[0]
    S = sc.strarr()[0]

    count = 0

    for i in range(1000):
        # print("--------")
        lucky = format_str(i)
        first = S.find(lucky[0])
        third = S.rfind(lucky[2])

        if first == -1 or third == -1:
            continue
        elif first < third:
            if lucky[1] in S[first + 1:third]:
                count += 1
    print(count)


def format_str(num):
    if num < 10:
        return "00" + str(num)
    elif num < 100:
        return "0" + str(num)
    else:
        return str(num)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


main()
### BUGGY CODE ###

a = int(input())
l = list(map(int,input().split()))
MOD = 998244353
dp = [0]*a
for i in l:
    dp[i]+=1
res = 1
# print(dp)
if dp[0] != 1 and l[0]!=0:
    print(0)
    exit()

for i in l[1:]:
    # print(i)
    res*=dp[i-1]

print(res%MOD)

### FIXED CODE ###

a = int(input())
l = list(map(int,input().split()))
MOD = 998244353
dp = [0]*a
for i in l:
    dp[i]+=1
res = 1
# print(dp)
if dp[0] != 1 and l[0]!=0:
    print(0)
    exit()

for i in l[1:]:
    # print(i)
    res*=dp[i-1]
    res%=MOD

print(res)
### BUGGY CODE ###

R, G, B, N = map(int,input().split())
count = 0
for i in range (N//R+1):
    for j in range (N//G+1):
        if (N - i*R - j*G)%B == 0 and (N - i*R - j*G)>=0:
            count += 1
print(count)

### FIXED CODE ###

R, G, B, N = map(int,input().split())
count = 0
i_range = N//R+1
j_range = N//G+1

for i in range (N//R+1):
    for j in range (N//G+1):
        if (N - i*R - j*G)%B == 0 and (N - i*R - j*G)>=0:
            count += 1
print(count)
### BUGGY CODE ###

s=input()
q=int(input())
for i in range(q):
    a=[_ for _ in input().split()]
    if a[0]=="1":
        s=s[::-1]
    elif a[1]=="1":
        s=a[2]+s
    else:
        s+=a[2]
print(s)

### FIXED CODE ###

s=input()
q=int(input())
muki=True
a=[[_ for _ in input().split()] for i in range(q)]
front=""
back=""
for i in a:
    if i[0]=="1":
        muki=not muki
        continue
    if (i[1]=="1" and muki) or (i[1]=="2" and not muki):
        front=i[2]+front
    else:
        back+=i[2]
if muki:
    print(front+s+back)
else:
    print((front+s+back)[::-1])
### BUGGY CODE ###

L=list(map(int,input()))
n=len(L)
X=pow(3,n-1)%(10**9+7)
count=1
for i in range(1,n):
    if L[i]==1:
        k=n-i-1
        count+=1
        X+=(pow(3,k)%(10**9+7))*(pow(2,count-1)%(10**9+7))
X+=pow(2,count)%(10**9+7)
print(X%(10**9+7))


### FIXED CODE ###

L=list(map(int,input()))
n=len(L)
def power(a,n):
    x=1
    L=list(format(n,'b'))
    l=len(L)
    for i in range(l):
        if int(L[l-i-1])==1:        
            x=(x*a)%(10**9+7)
        a=(a*a)%(10**9+7)
    return x
X=power(3,n-1)%(10**9+7)
count=1
for i in range(1,n):
    if L[i]==1:
        k=n-i-1
        count+=1
        X+=(power(3,k)%(10**9+7))*(power(2,count-1)%(10**9+7))
X+=power(2,count)%(10**9+7)
print(X%(10**9+7))
### BUGGY CODE ###

H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())

max_da=max(da)*10  
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for j in range(N):
    for i in range(H+max_da):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

print(min(dp[H:]))

### FIXED CODE ###

H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())

max_da=max(da) 
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for i in range(H+max_da):
    for j in range(N):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

print(min(dp[H:]))