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

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    #w={s}
    w=deque([0,s])
    tmp=[0]*(n+1)
    n*=3
    ans=0
    while n:
        n-=1
        ans+=1
        while 1:
            x=w.pop()
            if x==0:
                w.appendleft(0)
                break
            if x in d:
                for j in d[x]:
                    if tmp[j]!=ans:
                        w.appendleft(j)
                        tmp[j]=ans
        if ans%3==0 and tmp[t]==ans:
            print(ans//3)
            exit()
    print(-1)

if __name__=="__main__":
    sol()


### FIXED CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    #tmp=[0]*(n+1)
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

if __name__=="__main__":
    sol()
### BUGGY CODE ###

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

penal_ct = 0
ac_count = 0
# prev_ac_num = -1

ac_list = [False] * N

for i in range(M):
    if S[i] == 'AC' and (not ac_list[p[i] - 1]): # ACかつ今までにACしてない
        ac_list[p[i] - 1] = True
        ac_count += 1
        if i == 0:
            continue
        for j in range(i)[::-1]:
            if p[j] == p[i] and S[j] == 'WA':
                penal_ct += 1
    if all(ac_list):
        break



# for i in range(1, M)[::-1]:
#     if S[i] == 'AC' and p[i] != prev_ac_num:
#         prob_num = prev_ac_num = p[i]
#         ac_count += 1
#         for j in range(i)[::-1]:
#             if p[j] == prob_num and S[j] == 'WA':
#                 penal_ct += 1
print(ac_count, penal_ct) 


### FIXED CODE ###

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




penal_ct = 0
ac_count = 0
# prev_ac_num = -1
ac_list = [False] * N
pos = 0

wa_count = [0] * N

for i in range(M):
    if S[i] == 'WA':
        wa_count[p[i] - 1] += 1
        # print(wa_count[p[i] - 1])
    elif (not ac_list[p[i] - 1]) and S[i] == 'AC': # ACかつ今までにACしてない
        ac_list[p[i] - 1] = True
        ac_count += 1
        if i == 0:
            continue
        penal_ct += wa_count[p[i] - 1]
        # for j in range(i)[::-1]:
        #     if S[j] == 'WA' and p[j] == p[i]:
        #         penal_ct += 1
    # if all(ac_list):
        # break
# print(wa_count)
print(ac_count, penal_ct)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

num = 0
ans = 0
for r in range(N+1):
    numR = R*r
    if numR > N: continue
    for g in range(N+1):
        numG = numR + G*g
        if numG > N: continue
        b = (N-numG) / B
        if int(b) == b and b >= 0:
            ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

num = 0
ans = 0
for r in range(N+1):
    numR = R*r
    if numR > N: continue
    for g in range(N+1):
        numG = numR + G*g
        if numG > N: continue
        b = (N-numG) / B
        if int(b) == b and b >= 0:
            ans += 1

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

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

import math

flag = [a.count(a[i])-1 for i in range(n+1) ]
for i in range(n+1):
    p = flag.index(1) + list(reversed(flag)).index(1)
    if ( p>=i ):
        c = math.factorial(n+1)/math.factorial(i+1)/math.factorial(n-i) - math.factorial(p)/math.factorial(i)/math.factorial(p-i)
    else:
        c = math.factorial(n+1)/math.factorial(i+1)/math.factorial(n-i)
    print( int(c)%(10**9+7) )

### FIXED CODE ###


MOD = 10**9+7
n = int(input())
la = list(map(int,input().split()))
L = [-1]*(n+1)
l = 0
for i in range(n+1):
  a = la[i]
  if L[a] == -1:
    L[a] = i
  else:
    l = i - L[a] - 1
    break
 
MAX = n
factorial = [1, 1]
inverse = [0, 1]
inverse_factorial = [1, 1]
for i in range(2,MAX+1):
  factorial.append( (factorial[-1]*i)%MOD )
  inverse.append( (-inverse[MOD%i]*(MOD//i))%MOD )
  inverse_factorial.append( (inverse_factorial[-1]*inverse[-1])%MOD )
 
def C_MOD(n, k):
  if k < 0 or k > n:
    return 0
  k = min(k,n-k)
  return factorial[n] * inverse_factorial[k] * inverse_factorial[n-k] % MOD
 
print(n)
#print((2*C_MOD(n-1,1)-C_MOD(n-1-l,1)+C_MOD(n-1,2)+1)%MOD)
for i in range(2,n+1):
  if n > l+1:
    print((2*C_MOD(n-1,i-1)-C_MOD(n-1-l,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
  else:
    print((2*C_MOD(n-1,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
print(1)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    if a[-1] != 2:
        return -1
    b = 2
    c = 4
    for i in range(n-2,-1,-1):
        t = a[i]
        if b * 2 <= t:
            return -1
        if b % t == 0:
            pass
        elif b > t:
            b += t-b%t
        else:
            b = t
        if c % t == 0:
            pass
        elif c > t:
            c += t-c%t
        else:
            return -1
    bb = b
    cc = c-1
    while True:
        bb = b
        for i in range(n):
            bb -= bb%a[i]
        if bb != 2:
            b += a[0]
        else:
            break
    for i in range(n):
        cc -= cc%a[i]
    if cc != 2:
        return 1/0

    return '{} {}'.format(b, c-1)

print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

# 下がtrue, falseになる最小値を返す
def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n = I()
    a = LI()

    def f(i):
        for c in a:
            i -= i%c
        return i < 2

    def g(i):
        for c in a:
            i -= i%c
        return i <= 2

    mi = bs(f,0,sum(a)+3)
    ma = bs(g,0,sum(a)+3) - 1
    if mi <= ma:
        return '{} {}'.format(mi,ma)
    return -1




print(main())
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush

n, m, s, t = map(int, input().split())
c = 10**15
graph = defaultdict(list)
for _ in range(m):
  u, v, a, b = map(int, input().split())
  graph[u].append((v, a, b))
  graph[v].append((u, a, b))

dyen = defaultdict(lambda:float("INF"))
dsnuuk = defaultdict(lambda:float("INF"))
dyen[s] = 0
dsnuuk[t] = 0

def dijkstra(s, m):
  used = defaultdict(bool)
  q = []
  heappush(q, (0, s))

  while len(q):
    v = heappop(q)
    cost, cur = v[0], v[1]

    if used[v]:
      continue
    used[v]=True

    for to, a, b in graph[cur]:
      if m==0 and dyen[to]>cost+a:
        dyen[to] = cost+a
        heappush(q, (cost+a, to))
      elif m==1 and dsnuuk[to]>cost+b:
        dsnuuk[to] = cost+b
        heappush(q, (cost+b, to))

dijkstra(s, 0)
dijkstra(t, 1)

for i in range(n):
  ans = float("INF")
  for j in range(i+1, n+1):
    ans = min(ans, dyen[j]+dsnuuk[j])
  print(c-ans)

### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush

n, m, s, t = map(int, input().split())
c = 10**15
graph = defaultdict(list)
for _ in range(m):
  u, v, a, b = map(int, input().split())
  graph[u].append((v, a, b))
  graph[v].append((u, a, b))

dyen = defaultdict(lambda:float("INF"))
dsnuuk = defaultdict(lambda:float("INF"))
dyen[s] = 0
dsnuuk[t] = 0

def dijkstra(s, m):
  used = defaultdict(bool)
  q = []
  heappush(q, (0, s))

  while len(q):
    v = heappop(q)
    cost, cur = v[0], v[1]

    if used[v]:
      continue
    used[v]=True

    for to, a, b in graph[cur]:
      if m==0 and dyen[to]>cost+a:
        dyen[to] = cost+a
        heappush(q, (cost+a, to))
      elif m==1 and dsnuuk[to]>cost+b:
        dsnuuk[to] = cost+b
        heappush(q, (cost+b, to))

dijkstra(s, 0)
dijkstra(t, 1)

costs = [float("INF")]*(n+1)
min_ = float("INF")
for i in range(n, 0, -1):
  min_ = min(min_, dyen[i]+dsnuuk[i])
  costs[i] = min_

for i in range(1, n+1):
  print(c-costs[i])
### BUGGY CODE ###

import math

def combinations_count(n, r=2):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) if n > 1 else 0

N = int(input())
A = list(map(int, input().split()))
dp = [0]*(N+1)
cnt_org = {}

for a in A:
  key = str(a)
  cnt_org[key] = cnt_org.get(key, 0) + 1

for k in range(N):
  cnt = cnt_org.copy()
  cnt[str(A[k])] -= 1
  ans = 0
  for v in cnt.values():
    if dp[v] == 0:
      dp[v] = combinations_count(v)
    ans += dp[v]
  
  print(ans)



### FIXED CODE ###

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

dp = [int(n*(n-1)/2) for n in range(N+1)]
cnt_org = [0]*(N+1)

for a in A:
  key = a
  cnt_org[a] += 1 

base = sum([dp[c] for c in cnt_org])

for k in range(N):
  diff = dp[cnt_org[A[k]]] - dp[cnt_org[A[k]]-1]
  print(base - diff)
### BUGGY CODE ###

def issubset(a,b):
    #a<<bならtrue
    x=bin(a)[2:]
    y=bin(b)[2:]
    if a>b:
        return False
    for i in range(1,len(x)+1):
        if (x[-i],y[-i])==("1","0"):
            return False
    return True
N,K=map(int,input().split())
A=[0 for i in range(N)]
B=[0 for i in range(N)]
for i in range(N):
    A[i],B[i]=map(int,input().split())
Kl=[K]
Ks=bin(K)[2:]
for i,c in enumerate(Ks):
    if c=="1":
        Kl.append(int(Ks[:i]+"0"+"1"*(len(Ks)-i-1),2))
ans=0
for k in Kl:
    tmp=0
    for i in range(N):
        if issubset(A[i],k):
            tmp+=B[i]
    ans=max(tmp,ans)
print(ans)


### FIXED CODE ###

def issubset(x,y):
    #a<<bならtrue
    if len(x)>len(y):
        return False
    for i in range(1,len(x)+1):
        if (x[-i],y[-i])==("1","0"):
            return False
    return True
N,K=map(int,input().split())
A=[0 for i in range(N)]
B=[0 for i in range(N)]
for i in range(N):
    A[i],B[i]=map(int,input().split())
    A[i]=bin(A[i])[2:]
Ks=bin(K)[2:]
Kl=[Ks]
for i,c in enumerate(Ks):
    if c=="1":
        Kl.append(Ks[:i]+"0"+"1"*(len(Ks)-i-1))
ans=0
for k in Kl:
    tmp=0
    for i in range(N):
        if issubset(A[i],k):
            tmp+=B[i]
    ans=max(tmp,ans)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC89 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7


h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
s = [None for _ in range(h*w+1)]
for i in range(h):
    for j in range(w):
        s[a[i][j]] = [i+1,j+1]
D = [[0]*(h*w+1) for _ in range(d)]
for i in range(d+1,h*w+1):
    X,Y = s[i]
    Z,W = s[i-d]
    x = abs(X - Z) + abs(Y - W)
    D[i%d][i//d] = x + D[i%d][i//d-1]
for _ in range(q):
    l,r = map(int,input().split())
    print(D[l%d][r//d] - D[l%d][l//d])


### FIXED CODE ###

#!/usr/bin/env python3
#ABC89 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7


h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
s = [None for _ in range(h*w+1)]
for i in range(h):
    for j in range(w):
        s[a[i][j]] = [i+1,j+1]
D = [[0]*((h*w+1)//d+1) for _ in range(d)]
for i in range(d+1,h*w+1):
    X,Y = s[i]
    Z,W = s[i-d]
    x = abs(X - Z) + abs(Y - W)
    D[i%d][i//d] = x + D[i%d][i//d-1]
for _ in range(q):
    l,r = map(int,input().split())
    x = D[l%d]
    print(x[r//d] - x[l//d])
### BUGGY CODE ###

from heapq import heappush, heappop

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

MX = 2005
f_inf = float('inf')
dp = [[0 for _ in range(MX)] for _ in range(MX)]
dp[0][0] = 0

hq = []
for i in range(n):
    heappush(hq, (-A[i], i))

ans = 0
for i in range(n):
    x, pi = heappop(hq)
    for l in range(i+1):
        r = i-l
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + (pi-l)*A[pi])
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ((n-r-1)-pi)*A[pi])

ans = 0
for i in range(n+1):
    ans = max(ans, dp[n][i])
print(ans)

### FIXED CODE ###

from heapq import heappush, heappop

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

MX = 2005
f_inf = float('inf')
dp = [[0 for _ in range(MX)] for _ in range(MX)]
dp[0][0] = 0

hq = []
for i in range(n):
    heappush(hq, (-A[i], i))

ans = 0
for i in range(n):
    x, pi = heappop(hq)
    for l in range(i+1):
        r = i-l
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + (pi-l)*A[pi])
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ((n-r-1)-pi)*A[pi])

ans = 0
for i in range(n+1):
    ans = max(ans, dp[n][i])
print(ans)
### BUGGY CODE ###

from collections import defaultdict
MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = -(10 ** 100)

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = defaultdict(list)
    result = INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]

        if (pos == N - 1):
            result = max(result, cost)

        if (pos in visited):
            visited_cost = visited[pos][0]
            visited_cnt = visited[pos][1]
            if (visited_cost >= cost):
                continue
            if (visited_cnt >= MAX_N):
                continue
            visited[pos] = [cost, visited_cnt + 1]
        else:
            visited[pos] = [cost, 0]

        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]
            if (nxt not in visited):
                que.append([nxt, nxt_cost + cost])
            elif(nxt_cost + cost > visited[nxt][0]):
                que.append([nxt, nxt_cost + cost])
    if (visited[N - 1][1] >= MAX_N):
        return (0, False)
    return (result, True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)


### FIXED CODE ###


MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]
        if (visited[pos] > cost):
            continue
        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)
### BUGGY CODE ###

mod =1000000007
n = int(input())
a = list(map(int, input().split()))
sumpro = 0
x = 0
for i in range(n-1):
    x = 0
    for j in range(i+1, n):
        x += a[j]
        x = x%mod
    sumpro += (a[i]* x)%mod
        
print(sumpro%mod)

### FIXED CODE ###

MOD = 10 ** 9 + 7  # MODは変数に入れてしまったほうが打ち間違えなくていいです

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

S = sum(A) % MOD
ans = 0

# A_Nも含まれてしまいますが、そのときはs=0なので問題ありません
for x in A:
    S -= x  # 自分と自分自身を掛けないように、先に引く必要があります
    S %= MOD  # MODはいちいち取っておくといいです
    ans += S * x
    ans %= MOD

ans %= MOD  # この行は完全に不要ですが、最後だけMODを取り忘れてWAになるミスは非常によくあるので、必要以上に取っておくと安心できます
print(ans)
### BUGGY CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for __ in range(l + 1)]
    dp[0][0] = 1

    for i, si in enumerate(s):
        keta = pow(10, l - i - 1)
        if si == "?":
            for k in range(10):
                tmp = keta * k % 13
                for j in range(13):
                    dp[i + 1][(j + tmp) % 13] += dp[i][j]
                    dp[i + 1][(j + tmp) % 13] %= MOD
        else:
            si = int(si)
            tmp = keta * si % 13
            for j in range(13):
                dp[i + 1][(j + tmp) % 13] += dp[i][j]
                dp[i + 1][(j + tmp) % 13] %= MOD

    print(dp[l][5])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for __ in range(l + 1)]
    dp[0][0] = 1

    for i, si in enumerate(s):
        base = pow(10, l - i - 1, 13)

        if si == "?":
            for k in range(10):
                tmp = base * k % 13
                for j in range(13):
                    dp[i + 1][(j + tmp) % 13] += dp[i][j]
                    dp[i + 1][(j + tmp) % 13] %= MOD
        else:
            si = int(si)
            tmp = base * si % 13
            for j in range(13):
                dp[i + 1][(j + tmp) % 13] += dp[i][j]
                dp[i + 1][(j + tmp) % 13] %= MOD

    print(dp[l][5])


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

s = input()
l = len(s)
ans = 0
for i in range(l):
  for j in range(i+1, l+1):
    a =int(s[i:j])  
    if a % 2019 == 0:
      ans +=1
print(ans)

### FIXED CODE ###

s=input()[::-1]
ans=0
u=0
d=1
l=[0]*2019
l[0]=1
for i in map(int,s):
  u=(u+i*d)%2019
  l[u]+=1
  d=d*10%2019
for i in l:
  ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a.reverse() # aを大きい順にソート
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for i in range(n+1)]
for i in range(1,n+1):
    kouho = []
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == [0] * 10 and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                copy = dp[i-use[j]][:]
                copy[j] += 1
                kouho.append(copy)
    if kouho == []: #空の場合
        continue #何もしない
    else:
        usearray = []
        accnum = "0"
        for array in kouho:
            tmpnum = ""
            for k in range(9,0,-1):
                tmpnum += (str(k) * array[k])
            if int(tmpnum) > int(accnum):
                usearray = array
                accnum = tmpnum
        dp[i] = usearray
ans = ""
for i in range(9,0,-1):
    ans += (str(i) * dp[n][i])
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for i in range(n+1)]
for i in range(1,n+1):
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == [0] * 10 and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                if sum(dp[i-use[j]])+1 >= sum(dp[i]):
                    copy = dp[i-use[j]][:]
                    copy[j] += 1
                    dp[i] = copy
ans = ""
for i in range(9,0,-1):
    ans += (str(i) * dp[n][i])
print(ans)
### BUGGY CODE ###

K = int(input())
S = input()
N = len(S)
MOD = 10 ** 9 + 7


# 逆元の前計算
factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, K + N + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n - r)
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = 0
for i in range(K + 1):
    ans += pow(25, i, MOD) * nCr(i + N - 1, N - 1) * pow(26, K - i, MOD) % MOD
    ans %= MOD
print(ans % MOD)


### FIXED CODE ###

K = int(input())
S = input()
N = len(S)
MOD = 10 ** 9 + 7


# 逆元の前計算
factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, K + N + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n - r)
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = 0
for i in range(K + 1):
    ans += pow(25, i, MOD) * nCr(i + N - 1, N - 1) * pow(26, K - i, MOD) % MOD
    ans %= MOD
print(ans % MOD)