Harryxun/stf_run huggingface dataset:
def resolve():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    required = [10**18]+[2,5,5,4,5,6,3,7,6]
    dp = [0 for _ in range(N+1)]
    candidates = {}
    for a in A:
        req = required[a]
        if dp[req] < a:
            dp[req] = a
            candidates[req] = a
    #print(dp)
    #print(candidates)
    for i in range(N+1):
        for n_match, num in candidates.items():
            if i - n_match >= 0 and dp[i-n_match] != 0:
                dp[i] = max(dp[i], int(str(dp[i-n_match])+str(num)))
    #print(dp)
    print(dp[N])

if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    required = [None]+[2,5,5,4,5,6,3,7,6]
    dp = [0 for _ in range(max(10, N+1))]
    candidates = {}
    for a in A:
        req = required[a]
        if dp[req] < a:
            dp[req] = a
            candidates[req] = a
    #print(dp)
    #print(candidates)
    for i in range(N+1):
        for n_match, num in candidates.items():
            if i - n_match >= 0 and dp[i-n_match] != 0:
                dp[i] = max(dp[i], dp[i-n_match]*10+num)
    #print(dp)
    print(dp[N])

if '__main__' == __name__:
    resolve()
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


lim = 2*10**5   #必要そうな階乗の限界を入力

#階乗#
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


H, W, A, B = MAP()

ans = 0
for n in range(B, W):
	way = C(H-A-1+n, n)*C(W-n-1+A-1, A-1)%mod
	ans = (ans+way)%mod

print(ans)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

lim = 2*10**6
fact = [1]*(lim+1)
for n in range(1, lim+1):
	fact[n] = n*fact[n-1]%mod

fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod

H, W, A, B = MAP()

ans = 0
for n in range(B, W):
	way = C(H-A-1+n, n)*C(W-n-1+A-1, A-1)%mod
	ans = (ans+way)%mod

print(ans)
import sys


def find_paths(mat, n, m):

    dp = [[0 for i in range(m)] for j in range(n)]

    for i in range(n):

        if mat[i][0] != "#":
            dp[i][0] = 1

        else:
            break

    for j in range(m):

        if mat[0][j] != "#":
            dp[0][j] = 1

        else:
            break

    dp[0][0] = 0


    for i in range(1, n):
        for j in range(1, m):
            if mat[i][j] == "#":
                dp[i][j] = 0

            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    # print(dp)
    return int(dp[n - 1][m - 1] % (1e9+7))



n, m = list(map(int, sys.stdin.readline().split()))

mat = []

for i in range(n):
    mat.append([ch for ch in sys.stdin.readline().strip()])


dp = {}
# print(mat)
print(find_paths(mat, n, m))


### FIXED CODE ###

h, w = map(int, input().split())

mat = []
dp = []
m = 10**9+7

for i in range(h):
    mat.append(list(input()))
    dp.append(list([0]*w))

dp[0][0] = 1


for x in range(h):
    for y in range(w):

        if x != 0 or y != 0:
            if mat[x][y] == "#":
                dp[x][y] = 0

            else:
                dp[x][y] += (dp[x - 1][y] + dp[x][y - 1]) % m

print(dp[h - 1][w - 1])
n=int(input())
l=list(map(int,input().split()))
if min(l)=0:
    print(0)
else:    
    s=1
    for x in l:
        s *= x
    
    if s>1000000000000000000:
        print(-1)
    else:
        print(s)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
if min(l)== 0:
    print(0)
else:    
    s=1
    for x in l:
        s *= x
        if s>10**18:
            s=-1
            break
    print(s)
11 4

### FIXED CODE ###

A, B = [int(i) for i in input().split()]

if A > 8 or B > 8:
    print(":(")
else:
    print("Yay!")
s = input()

for i in range(len(s)):
    if s[i] == 'A':
        a_index = i

for j in range(-1, -(len(s)-a_index), -1):
    if s[j] == 'Z':
        z_index = j

length = (len(s) + z_index) - a_index + 1
print(length)


### FIXED CODE ###

s = input()

for i in range(len(s)):
    if s[i] == 'A':
        a_index = i
        break

for j in range(-1, -(len(s)-a_index), -1):
    if s[j] == 'Z':
        z_index = j
        break

length = (len(s) + z_index) - a_index + 1
print(length)
h, w = map(int, input().split())

s = [input() for _ in range(h)]

ans = 'Yes'

for i in range(1, h):
    for j in range(1, w):
        if s[i][j] == '#' and s[i-1][j] == '.' and s[i+1][j] == '.' and s[i][j-1] == '.' and s[i][j+1] == '.':
            ans = 'No'

print(ans)


### FIXED CODE ###

h, w = map(int, input().split())

s = [input() for _ in range(h)]

ans = 'Yes'

for i in range(1, h-1):
    for j in range(1, w-1):
        if s[i][j] == '#' and s[i-1][j] == '.' and s[i+1][j] == '.' and s[i][j-1] == '.' and s[i][j+1] == '.':
            ans = 'No'

print(ans)
n = int(input())
s = input()
k = int(input())


for i in range(0,n):
  if s[i] != s[k-1]:
    s[i] = '*'

print(s)

### FIXED CODE ###

n = int(input())
s = list(input())
k = int(input())
 
 
for i in range(0,n):
  if s[i] != s[k-1]:
    s[i] = '*'

s = "".join(s)
print(s)
def main():
    a,b,c = list(map(int, input().split()))
    if a[-1] == b[0] and b[-1] == c[0]:
        print('YES')
    else:
        print('NO')

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    a,b,c = input().split(' ')
    if a[-1] == b[0] and b[-1] == c[0]:
        print('YES')
    else:
        print('NO')

if __name__ == '__main__':
    main()
a, b = map(int.input().split())
print(a * b, a * 2 + b * 2) 

### FIXED CODE ###

a, b = map(int, input().split())
print(a * b, a * 2 + b * 2)
import numpy as np


N = int(input())
abc = []
for n in range(N):
    abc.append(list(map(int, input().split())))

# initialize
dp = np.zeros((N+1, 3))

# dp    
for i in range(N+1):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            try:
                dp[i+1][k] = max(dp[i+1][k], dp[i][j] + abc[i][k])
            except:
                pass

print(int(max(dp[-1])))


### FIXED CODE ###

N = int(input())
abc = []
for n in range(N):
    abc.append(list(map(int, input().split())))

# initialize
dp = [[-float("inf")]*3 for i in range(N+1)]
for i in range(3):
    dp[0][i] = 0

# dp    
for i in range(N+1):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            try:
                dp[i+1][k] = max(dp[i+1][k], dp[i][j] + abc[i][k])
            except:
                pass

print(int(max(dp[-1])))
N = list(map(int,input()))
k = int(input())

for i in range(k):
  if N[1] <= N[0]:
    N[1] = N[1] * 2
  elif N[2] <= N[0]:
    N[2] = N[2] * 2
  
if N[1] >= N[0] and N[2] >= N[0]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

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

for i in range(k):
  if N[1] <= N[0]:
    N[1] = N[1] * 2
  elif N[2] <= N[1]:
    N[2] = N[2] * 2
  
if N[1] > N[0] and N[2] > N[1]:
  print("Yes")
else:
  print("No")
from math import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd, numbers)

N,X=list(map(int,input().split()))
x=list(map(int,input().split()))
x.append(X)
x.sort()
y=[]

for i in range(N):
    y.append(x[i+1]-x[i])
print(gcd_list(y))

### FIXED CODE ###

N,X=map(int, input().split())
x=list(map(int, input().split()))

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

x.append(X)
y=sorted(x)
z=[]
for i in range(N):
    z.append(y[i+1]-y[i])
Min=z[0]
for i in range(N-1):
    if Min>gcd(z[i],z[i+1]):
        Min=gcd(z[i],z[i+1])
print(Min)
n = int(input())
apple = []
for _ in range(n):
    a = str(input())
    if a not in apple:
        apple.append(a)
    else:
        apple.remove(a)
print(len(apple))

### FIXED CODE ###

n = str(input())
print("Yes" if "9" in n else "No")
N, M = map(int, input().split())
a = [0] * M
for i in range(M):
    a[i] = int(input())

mod = 10 ** 9 + 7

dp = [0] * 100010

j = 0
dp[0] = 1
if a[0] == 1:
    dp[1] = 0
    j += 1
else:
    dp[1] = 1

a += [-1]
for i in range(2, N+1):
    if i == a[j]:
        dp[i] = 0
        j += 1
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod

print(dp[N] % mod)

### FIXED CODE ###

N, M = map(int, input().split())
a = [0] * M
for i in range(M):
    a[i] = int(input())

mod = 10 ** 9 + 7

dp = [0] * 100010

j = 0
dp[0] = 1
if M > 0:
    if a[0] == 1:
        dp[1] = 0
        j += 1
    else:
        dp[1] = 1
else:
    dp[1] = 1

a += [-1]
for i in range(2, N+1):
    if M > 0:
        if i == a[j]:
            dp[i] = 0
            j += 1
            continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[N] % mod)
n = int(input())
t,a = map(int,input().split())
h = list(map(int, input().split()))
k = []
for i in h:
  k.append(abs(t - a - i * 0.006))
print(hh.index(min(k))+1)

### FIXED CODE ###

n = int(input())
t,a = map(int,input().split())
h = list(map(int, input().split()))
k = []
for i in h:
  k.append(abs(t - a - i * 0.006))
print(k.index(min(k))+1)
import math 
import bisect
import heapq
from collections import deque

n = int(input())
print(n(n-1) //2)

### FIXED CODE ###

import math 
import bisect
import heapq
from collections import deque

n = int(input())
print(n*(n-1) // 2)
n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[]
  y=[]
  for j in range(a):
    x,y=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
c=0
for i in range(n):
  #l=[1]*n
  #for j in range(i, n-i):
    #if l[j]==0:continue
    #for k in range(A[j]):
      #b=X[j][k]
      #l[b] *= Y[j][k]

if c < l.count(1):
  c=l.count(1) 
  
        
  
print(c)  
   

### FIXED CODE ###

n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c and d==0:
    s=c
      
      
print(s)
K, S = map(int, input().split())

X = []


def dfs(A):
    if len(A) == 3:
        if A[0] + A[1] + A[2] == S:
            X.append(A.copy())
        return
    for i in range(K + 1):
        A.append(i)
        dfs(A)
        A.pop()


dfs([])
print(len(X))


### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z <= K:
            count = count + 1

print(count)
S = input()
S[3]=str("8")
print(S)

### FIXED CODE ###

S = input()
print(S[:3]+"8"+S[4:])
s = list(str(input()))
x,y = map(int,input().split())

i = 0
while i < len(s) and s[i] =="F":
    i += 1
x -= i
s = s[i+1:]

m = [[],[0]]
num = 1

for i in range(len(s)):
    if s[i] == "F":
        m[num][-1] += 1
    else:
        num += 1
        num %= 2
        m[num].append(0)

#print("m",m)

sumx = sum(m[0])
dpx = [False]*(2*sumx+3) #index(sumx+1)が座標0
dpx[sumx+1] = True
#print("dpx",dpx)

for p in m[0]:
    dpx_pre = dpx[:]
    dpx = [False]*(2*sumx+3)
    for i in range(2*sumx+3):
        if i-p >= 0 and (dpx[i-p] == False):
            dpx[i-p] = dpx_pre[i]
            #print("dpx",dpx)
        if i+p < 2*sumx+3 and (dpx[i+p] == False):
            dpx[i+p] = dpx_pre[i]
            #print("dpx",dpx)
    #print("dpx",dpx)

sumy = sum(m[1])
dpy = [False]*(2*sumy+3) #index(sumy+1)が座標0
dpy[sumy+1] = True
#print("dpy",dpy)

for p in m[1]:
    dpy_pre = dpy[:]
    dpy = [False]*(2*sumy+3)
    for i in range(2*sumy+3):
        if i-p >= 0 and (dpy[i-p] == False):
            dpy[i-p] = dpy_pre[i]
        if i+p < 2*sumy+3 and (dpy[i+p] == False):
            dpy[i+p] = dpy_pre[i]
    #print("dpy",dpy)

if dpx[x+(sumx+1)] == True and dpy[y+(sumy+1)] == True:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = list(str(input()))
x,y = map(int,input().split())

i = 0
while i < len(s) and s[i] =="F":
    i += 1
x -= i
s = s[i:]

m = [[],[]]
num = 0

for i in range(len(s)):
    if s[i] == "F":
        m[num][-1] += 1
    else:
        num += 1
        num %= 2
        m[num].append(0)

#print("m",m)

sumx = sum(m[0])

dpx = [False]*(2*sumx+3) #index(sumx+1)が座標0
dpx[sumx+1] = True
#print("dpx",dpx)

for p in m[0]:
    dpx_pre = dpx[:]
    dpx = [False]*(2*sumx+3)
    for i in range(2*sumx+3):
        if i-p >= 0:
            dpx[i-p] = dpx_pre[i] or dpx[i-p]
            #print("dpx",dpx)
        if i+p < 2*sumx+3:
            dpx[i+p] = dpx_pre[i] or dpx[i+p]
            #print("dpx",dpx)
    #print("dpx",dpx)

sumy = sum(m[1])
dpy = [False]*(2*sumy+3) #index(sumy+1)が座標0
dpy[sumy+1] = True
#print("dpy",dpy)

for p in m[1]:
    dpy_pre = dpy[:]
    dpy = [False]*(2*sumy+3)
    for i in range(2*sumy+3):
        if i-p >= 0:
            dpy[i-p] = dpy_pre[i] or dpy[i-p]
        if i+p < 2*sumy+3:
            dpy[i+p] = dpy_pre[i] or dpy[i+p]
    #print("dpy",dpy)

if abs(x) > sumx+1 or abs(y) > sumy+1:
    print("No")
elif dpx[x+(sumx+1)] and dpy[y+(sumy+1)]:
    print("Yes")
else:
    print("No")
import collections
n = int(input())
v = list(map(int, input().split()))
even = [v[2*i] for i in range(n//2)]
odd = [v[2**i+1] for i in range(n//2)]
dEven = collections.Counter(even).most_common()
dOdd = collections.Counter(odd).most_common()
if dEven[0][0] != dOdd[0][0]:
    ans = n - dEven[0][1]  - dOdd[0][1]
else:
    ans = n - max(dEven[0][1]+dOdd[1][0], dEven[1][0]+dOdd[0][1])
print(ans)

### FIXED CODE ###

import collections
n = int(input())
v = list(map(int, input().split()))
even = [v[2*i] for i in range(n//2)]
odd = [v[2*i+1] for i in range(n//2)]
dEven = collections.Counter(even).most_common()
dOdd = collections.Counter(odd).most_common()
if dEven[0][0] != dOdd[0][0]:
    ans = n - dEven[0][1]  - dOdd[0][1]
else:
    if len(dEven) >=2 and len(dOdd) >= 2:
        ans = n - max(dEven[0][1]+dOdd[1][1], dEven[1][1]+dOdd[0][1])
    elif len(dEven) < len(dOdd):
        ans = n - (dEven[0][1]+dOdd[1][1])
    elif len(dEven) > len(dOdd):
        ans = n - (dEven[1][1]+dOdd[0][1])
    else:
        ans = n//2
print(ans)
import sys
import os

def file_input():
    f = open('AGC009/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    N=int(input())
    A=[]
    B=[]
    for i in range(N):
        tmp=list(map(int, input().split()))
        A.append(tmp[0])
        B.append(tmp[1])

    cnt=0
    for j in range(N):
        # while (A[N-1-j]+cnt)%B[N-1-j]!=0:
        # cnt+=1
        tmp=A[N-1-j]+cnt
        if not tmp==0:
            # cnt=B[N-1-j]
            elif tmp<B[N-1-j]:
                cnt+=B[N-1-j]-tmp
            elif tmp%B[N-1-j]!=0:
                cnt+=B[N-1-j]-tmp%B[N-1-j]

    print(cnt)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os

def file_input():
    f = open('AGC009/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    N=int(input())
    A=[]
    B=[]
    for i in range(N):
        tmp=list(map(int, input().split()))
        A.append(tmp[0])
        B.append(tmp[1])

    cnt=0
    for j in range(N):
        # while (A[N-1-j]+cnt)%B[N-1-j]!=0:
        # cnt+=1
        tmp=A[N-1-j]+cnt
        if not tmp==0:
            # cnt=B[N-1-j]
            if tmp<B[N-1-j]:
                cnt+=B[N-1-j]-tmp
            elif tmp%B[N-1-j]!=0:
                cnt+=B[N-1-j]-tmp%B[N-1-j]

    print(cnt)

if __name__ == '__main__':
    main()
s=sort(input())
if (s[0]==s[1]) and (s[2]==s[3])　and (s[0]!=s[2]):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

s=sorted(input())
if (s[0]==s[1]) and (s[2]==s[3]) and (s[0]!=s[2]):
    print("Yes")
else:
    print("No")
n,k=map(int,input().split())
num=0
for i in range(k,n+2):
    num+=i*(n-i+1)+1
print(num%(10**9+7))

### FIXED CODE ###

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

num=[0]*N
for i in A:
    num[i-1]+=1

for j in range(len(num)):
    print(num[j])
import itertools
def prdct(array):
	ref = 1
	for a in array: ref *= a
	return ref

while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	p = sorted(map(int,raw_input().split()))
	if 1 in p:
		print 0.0
		continue
	for i in range(len(p)-1,0,-1):
		for j in range(i):
			while 1:
				if p[i] == p[j]:
					del p[i]
					break
				elif p[i]%p[j] == 0:
					p[i] /= p[j]
				else:
					break
	d = sum(pi*(n/pi*(n/pi+1))/2 for pi in p)
	m = sum(n/pi for pi in p)
	q = []
	for i in range(2,len(p)+1):
		q += [prdct(element) for element in itertools.combinations(p,i)]
	d -= sum(qi*(n/qi*(n/qi+1))/2 for qi in q)
	m -= sum(n/qi for qi in q)
	print (n*(n+1)/2-d)*1.0/(n-m) if n-m > 0 else 0.0

### FIXED CODE ###

while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	p = min(map(int,raw_input().split()))
	print n/2.0 if p > 1 else 0.0
import math

finished = False
solutions = []

def rec(A, B, n):
    global solutions
    global N

    if (A == B):
        solutions.append(n)

    if (math.floor(N/2) > n):
        if A == 1:
                rec(A+1, B+1, n+1)
                rec(A+1, B-1, n+1)
                rec(A, B+1, n+1)
                rec(A, B-1, n+1)
        elif A == N:
                rec(A, B+1, n+1)
                rec(A, B-1, n+1)
                rec(A-1, B+1, n+1)
                rec(A-1, B-1, n+1)
        elif B == 1:
                rec(A+1, B+1, n+1)
                rec(A+1, B, n+1)
                rec(A-1, B+1, n+1)
                rec(A-1, B, n+1)
        elif B == N:
                rec(A+1, B, n+1)
                rec(A+1, B-1, n+1)
                rec(A-1, B, n+1)
                rec(A-1, B-1, n+1)
        else:
                rec(A+1, B+1, n+1)
                rec(A+1, B-1, n+1)
                rec(A-1, B+1, n+1)
                rec(A-1, B-1, n+1)

in_string = input()
in_arr = in_string.split()
global N
global A
global B
N = int(in_arr[0])
A = int(in_arr[1])
B = int(in_arr[2])

rec(A, B, 0)
solutions.sort()
print(solutions[0])

### FIXED CODE ###

in_string = raw_input()
in_arr = in_string.split()
N = int(in_arr[0])
A = int(in_arr[1])
B = int(in_arr[2])

if ((B-A) % 2) == 0:
    print(int((B-A)/2))
else:
    if (N-B) > A-1:
        print(int(A+(B-A-1)/2))
    else:
        print(int(N-B+1+((N-(A+N-B+1))/2)))
n = int(input())
a_ls = list(map(int, input().split()))
hats_person = [1,0,0]
ans = 3
mod = 10**9+7
for i in range(1,n):
    same = a_ls[i]
    n_choices = 0
    choice_ind = -1
    for j,person in enumerate(hats_person):
        if person == same:
            n_choices += 1
            choice_ind = j
    if choice_ind == -1:
        print(0)
        sys.exit()
    hats_person[choice_ind] += 1
    ans *= n_choices
    ans %= mod
print(ans%mod)

### FIXED CODE ###

import sys
n = int(input())
a_ls = list(map(int, input().split()))
hat_nperson = [0,0,1]
ans = 3
mod = 10**9+7

if a_ls[0] != 0 or (n != 1 and a_ls[1] == 2):
    print(0)
    sys.exit()

for i in range(1,n):
    n_same = a_ls[i]
    n_choices = 0
    choice_ind = -1
    for j,person in enumerate(hat_nperson):
        if person == n_same:
            n_choices += 1
            choice_ind = j
    if choice_ind == -1:
        print(0)
        sys.exit()
    hat_nperson[choice_ind] += 1
    ans *= n_choices
    ans %= mod
print(ans%mod)
n = int(input())
ls = []
for _ in n:
  ls.append(input())
  
 print(len(set(ls)))


### FIXED CODE ###

n = int(input())
ls = []
for _ in range(n):
  ls.append(input())
  
print(len(set(ls)))
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)

def main():
    mod = 998244353
    N, K = map(int, input().split())
    L = [0] * K
    R = [0] * K
    for i in range(K):
        L[i], R[i] = map(int, input().split())

    S = set()
    for i in range(K):
        for j in range(L[i], R[i] + 1):
            S.add(j)

    dp = [0] * N
    dp[0] = 1
    for s in S:
        dp[s] += 1
    for i in range(N):
        if dp[i] != 0:
            for s in S:
                if i + s <= N - 1:
                    dp[i + s] += 1
    print(dp[N - 1] % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)


def main():
    MOD = 998244353
    N, K = map(int, input().split())
    L = [0] * K
    R = [0] * K
    for i in range(K):
        L[i], R[i] = map(int, input().split())

    dp = [0] * (N + 1)
    dpsum = [0] * (N + 1)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N + 1):
        for j in range(K):
            li = i - R[j]
            li = max(li, 1)
            ri = i - L[j]
            if ri < 0:
                continue
            dp[i] += (dpsum[ri] - dpsum[li - 1]) % MOD
        dpsum[i] += (dpsum[i - 1] + dp[i]) % MOD
    print(dp[N] % MOD)


if __name__ == '__main__':
    main()
import itertools

n, m, q = map(int, input().split())


n, m, q = map(int, input().split())
query = []
for i in range(q):
    query.append(list(map(int, input().split())))

choices = list(itertools.combinations_with_replacement([i for i in range(1, m+1)], n))
ans = -1
for choice in choices:
    score = 0
    for q in query:
        if choice[q[1]-1] - choice[q[0]-1] == q[2]:
            score += q[3]
    ans = max(ans, score)
print(ans)

### FIXED CODE ###


import itertools


n, m, q = map(int, input().split())
query = []
for i in range(q):
    query.append(list(map(int, input().split())))

choices = list(itertools.combinations_with_replacement([i for i in range(1, m+1)], n))
ans = -1
for choice in choices:
    score = 0
    for q in query:
        if choice[q[1]-1] - choice[q[0]-1] == q[2]:
            score += q[3]
    ans = max(ans, score)
print(ans)