Harryxun/stf_run huggingface dataset:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])[1]


def dp(N, B, min_):
    if N // min_ == 1:
        for a, n in B:
            if n == N:
                return [a]
        return None
    else:
        for a, n in B:
            if (n - min_) <= (N % min_):
                ret = dp(N-n, B, min_)
                if ret is None:
                    continue
                else:
                    return [a] + ret


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

### FIXED CODE ###

from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
a_min, n_min = min(B, key=lambda x: x[1])
g = [(a, n-n_min) for a, n in B if a > a_min and n > n_min]
l = [(a, n-n_min) for a, n in B if a < a_min and n > n_min]
l.sort(key=lambda x: x[1], reverse=True)
C = g + l

def dp(rem, C):
    ret = None
    if rem == 0:
        ret = []
    elif rem > 0:
        for i in range(len(C)):
            a, m = C[i]
            nxt = dp(rem-m, C[i:])
            if nxt is not None:
                ret = [a] + nxt
                break
    return ret


i = 0
while True:
    quo = N // n_min - i
    rem = N % n_min + i * n_min
    lst = dp(rem, C)
    if lst is not None:
        lst = sorted(lst + [a_min] * (quo-len(lst)), reverse=True)
        print(''.join(map(str, lst)))
        break
    i += 1
a=input()
a=a.split()

x=str(a[0])
y=str(a[1])

y=txt[:-1]

if x=y:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

x=input()
b=input()

y=b[:-1]

if x==y:
  print("Yes")
else:
  print("No")
N = int(input())
M = int(input())

if N == M:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

N, M = input().split()

if N == M:
  print('Yes')
else:
  print('No')
while True:
    n = int(raw_input())
    if n == 0: break

    for i in range(n):
        x = map(int, raw_input().split())
        ave = sum(x) / n
    std = (sum([(e-ave)**2 for e in x])/n)**0.5
    print std

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0: break

    x = map(int, raw_input().split())
    ave = sum(x) / float(n)
    std = (sum([(e-ave)**2 for e in x])/n)**0.5
    print std
a,b = map(int,input().split())

c = input().split()

while 1:
    f = 1
    s = str(c)
    for i in c:
        if i in c: f = 0
    if f : break
    c += 1
print(c)

### FIXED CODE ###

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

c = input().split()

while 1:
    f = 1
    s = str(a)
    for i in c:
        if i in s: f = 0
    if f : break
    a += 1
print(a)
import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
px = [ list(map(int,input().split())) for _ in range(q) ]
# print(tree)
# print(px)
c = [0]*n
for i in range(len(px)):
    c[px[i][0]-1] += px[i][1]
# print(c)
# for i in range(1,n):
#     c[i] += c[min(tree[i])-1]
visited = [0]*n
visited[0] = 1
while sum(visited)=n:
    for i in range(1,n):
        for j in range(len(tree[i])):
            node_tmp = tree[i][j]
            if visited[node_tmp-1]==1 and visited[i]==0:
                c[i] += c[node_tmp-1]
                visited[i] = 1
            else:
                pass
print(" ".join(map(str,c)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
# px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
# for i in range(len(px)):
for _ in range(q):
    p,x = map(int,input().split())
    c[p-1] += x  
visited = [0]*n
cnd = [1]   # current_node
while len(cnd)>0:
    nnd = []
    for j in cnd:
        visited[j-1]=1
        ko = tree[j-1]
        for k in ko:
            if visited[k-1]==0:
                c[k-1] += c[j-1]
                nnd.append(k)
    cnd = nnd
print(" ".join(map(str,c)))
N=int(input())
A=int(input())

if N%500 =< A :
    print("YES")
else :
    print("NO")

### FIXED CODE ###

n=int(input())
a=int(input())

print("Yes") if n%500<=a else print("No")
n=int(input())
ls=input().split(' ')
mp=[]
for i in range(min(ls),max(ls)+1):
    hp=0
    for j in range(n):
        hp+=(i-int(ls[j]))**2
    mp.append(hp)
print(min(mp))

### FIXED CODE ###

n=int(input())
ls=input().split(' ')
mp=[]
for i in range(100):
    hp=0
    for j in range(n):
        hp+=(i-int(ls[j]))**2
    mp.append(hp)
print(min(mp))
a, op, b = input().split()
a = int(a)
b = int(b)
print(a op b)

### FIXED CODE ###

a, op, b = input().split()
a = int(a)
b = int(b)
if op == '+':
    print(a + b)
else:
    print(a - b)
n = int(input())

B_lst = list(map(int,input().split()))
A_lst = [0] * (n+1)

for i in range(n):
    if B_lst[i] > B_lst[i-1]:
        A_lst[i] = str(B_lst[i-1])
    else:
        A_lst[i] = str(B_lst[i])

    if i == n-1:
        A_lst[i+1] = str(B_lst[i])
        break

list = ' '.join(A_lst)
print(list)


### FIXED CODE ###

n = int(input())

B_lst = list(map(int,input().split()))
A_lst = [0] * n

A_lst[0] = B_lst[0]
A_lst[n-1] = B_lst[n-2]

if n >= 3:
    for i in range(1,n-1):

        if B_lst[i-1] > B_lst[i]:
            A_lst[i] = B_lst[i]
        else:
            A_lst[i] = B_lst[i-1]

print(sum(A_lst))
a,b,c=input().split()

if a==b==5:
  if c==7:
    return print("Yes")
  else:
    return print("No")
elif a==c==5:
  if b==7:
    return print("Yes")
  else:
    return print("No")
elif b==c==5:
  if a==7:
    return print("Yes")
  else:
    return print("No")
else:
  return print("No")

### FIXED CODE ###

abc=list(map(int,input().split()))
abc.sort()
if abc ==[5, 5, 7]:
  print("YES")
else:
  print("NO")
s = list(input())
l = []
for i in range(s):
  if i == "1":
    l.append("9")
  elif i == "9":
    l.append("1")
  else:
    l.append(i)
for k in l:
  print(k,end="")

### FIXED CODE ###

s = input()
l = []
for i in range(len(s)):
  if s[i] == "1":
    l.append("9")
  elif s[i] == "9":
    l.append("1")
  else:
    l.append(s[i])
for k in l:
  print(k,end="")
inp = input().split("")
lis = [,]
for i in range(inp[0]):
  lis[1] += inp[1]
for i in range(inp[1]):
  lis[0] += inp[0]
lis.sort()
print(lis[0])

### FIXED CODE ###

hoge = input().split(" ")
a=""
b=""
for i in range(int(hoge[1])):
  a += hoge[0]
for i in range(int(hoge[0])):
  b += hoge[1]
txt = [a,b]
txt.sort()
print(txt[0])
n, q = map(int, input().split())

edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edge[a-1].append(b)
    edge[b-1].append(a)

cnt = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x


def dfs(now, bef):
    for nxt in edge[now-1]:
        if nxt != bef:
            cnt[nxt-1] += cnt[now-1]
            dfs(nxt, now)


dfs(1, 0)
print(*cnt)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)


def input(): return sys.stdin.readline()


N, Q = map(int, input().split())
ab = [[] for _ in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)

P = [0 for _ in range(N)]
for i in range(Q):
  p, x = map(int, input().split())
  P[p-1] += x


def dfs(p, par):
  for i in ab[p-1]:
    if i != par:
      P[i-1] += P[p-1]
      dfs(i, p)


dfs(1, -12345)
print(" ".join(map(str, P)))
import sys
n = input()
a = [[[0]*10 for i in range(3)] for i in range(4)]
for i in xrange(n):
	b = map(int, raw_input().split())
	a[b[0]-1][b[1]-1][b[2]-1] += b[3]

for i in range(4):
	for j in range(3):
		for k in range(10):
			sys.stdout.write(' %s' % a[i][j][k])
		print ""
	if i != 3
	print '#'*20

### FIXED CODE ###

import sys
n = input()
a = [[[0]*10 for i in range(3)] for i in range(4)]
for i in xrange(n):
	b = map(int, raw_input().split())
	a[b[0]-1][b[1]-1][b[2]-1] += b[3]

for i in range(4):
	for j in range(3):
		for k in range(10):
			sys.stdout.write(' %s' % a[i][j][k])
		print ""
	if i != 3:
		print '#'*20
N, K = map(int,input().split())
li = []

for i in range(N):
        li.append(int(input()))

li.sort()

co = K - 1
hmin = 1000000
for i in range(N-K+2):
        if hmin > li[i+co] - li[i]:
                hmin = li[i+co] - li[i]
                if hmin == 0:
                        break
print(hmin)

### FIXED CODE ###

N, K = map(int,input().split())
li = []

for i in range(N):
        li.append(int(input()))

li.sort()

co = K - 1
hmin = li[co] - li[0]
for i in range(N-K+1):
        if hmin > li[i+co] - li[i]:
                hmin = li[i+co] - li[i]
                if hmin == 0:
                        break
print(hmin)
S = input()
n = len(S)-1
total_num = 0
for i in range(2**n):
    num = '' 
    for j in range(n):
        if i & 2**j:
            num += S[j]
            total_num += int(num)
            num = ''
        else:
            num += S[j]
    num += S[j+1]
    total_num += int(num)
print(total_num)

### FIXED CODE ###

S = input()
n = len(S)-1
total_num = 0
if n == 0:
    total_num = S[0]
else:
    for i in range(2**n):
        num = '' 
        for j in range(n):
            if i & 2**j:
                num += S[j]
                total_num += int(num)
                num = ''
            else:
                num += S[j]
        num += S[-1]
        total_num += int(num)
print(total_num)
a,b,c = map(int,input().split())
if a+c => b:
    print(b)
else:
    print(a+c)

### FIXED CODE ###

a,b,c = map(int,input().split())
if b+c >= a:
    print(c-a+b)
else:
    print(0)
#106b
n = int(input())
ans=0
for i in range(1,n+1,2):
    c=0
    for j in range(1,i+1):
        if i%j==0:
            c+=1
            
    if c==8:
        a+=1
print(ans)

### FIXED CODE ###

#107b
n=int(input())


if n<105:
    print(0)
elif n<135:
    print(1)
elif n<165:
    print(2)
elif n<189:
    print(3)
elif n<195:
    print(4)
else:
    print(5)
sec=int(input())
h=inr(sec/3600)
m=int((sec-(3600*h))/60)
s=int(sec-(3600*h)-(60*m))
print("{0}:{1}:{2}".format(h,m,s))


### FIXED CODE ###

sec=int(input())
h=int(sec/3600)
m=int((sec-(3600*h))/60)
s=int(sec-(3600*h)-(60*m))
print("{0}:{1}:{2}".format(h,m,s))
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
chk = []
for i in range(n):
  a,b =  map(int,input().split())
  if a <= m:
    chk.append((a,b))

from heapq import heappop, heappush
from operator import itemgetter
chk = sorted(chk,key=itemgetter(0),reverse=True)

q = []
ans = 0
for i in range(1, m + 1):
    while chk and chk[-1][0] <= i:
        a,b = chk.pop()
        heappush(q,-b)
    if q:
        ans -= heappop(q)
print(ans)

### FIXED CODE ###

from collections import deque
def use_path(n,start,es):
    q = deque()
    chk = [False] * n
    q.append(start)
    chk[start] = True
    used = {start}
    while len(q) > 0:
        node = q.popleft()
        for nex in es[node]:
            if not chk[nex]:
                chk[nex] = True
                q.append(nex)
                used.add(nex)
    return used
  
def belman(s,g,n,es):
    d = [10**10] * n
    d[s] = 0
    fin = False
    cnt = 0
    while True:
      update = False
      for p,q,r in es:
        if d[p] != 10**10 and d[q] > d[p] + r:
          d[q] = d[p] + r
          update = True
      cnt += 1
      if not update:
        fin = True
        break
      if cnt > n+1:
          break      
    if fin:
        return max(0,-d[g])
    else:
        return -1   
  
n,m,p = map(int, input().split())

l = [[] for i in range(n)]
r = [[] for i in range(n)]
edges = []

for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    r[b].append(a)
    edges.append((a,b,-c+p))
    
use_nodes = use_path(n,0,l) & use_path(n,n-1,r)
es = [(a,b,c) for a,b,c in edges if a in use_nodes and b in use_nodes]
print(belman(0,n-1,n,es))
import numpy as np

N, K = map(int, input().split())

mat = np.array([[False] * N for i in range(N)])

for i in range(K):
    d = int(input())
    a = list(map(int, input().split()))
    for j in range(d):
        mat[i][a[j]-1] = True

mat = mat.T


ans = 0
for i in range(N):
    flg = False
    for j in range(N):
        if mat[i][j]:
            flg = True

    if not flg:
        ans += 1

print(ans)

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())

mat = np.array([[False] * N for i in range(K)])

for i in range(K):
    d = int(input())
    a = list(map(int, input().split()))
    for j in range(d):
        mat[i][a[j]-1] = True

mat = mat.T

ans = 0
for i in range(N):
    flg = False
    for j in range(K):
        if mat[i][j]:
            flg = True

    if not flg:
        ans += 1

print(ans)
n = int(input())
a = list(map(int, input().split()))
q = int(input())
x = [0] * 100001
ans = sum(a)

for ai in a:
    x[ai] += 1  # xのなかでaiが登場する個数のカウント

for _ in range(q):
    b, c = map(int, input().split())
    ans += (c-b) * x[b]
    x[c] += x[b]  # bをcに入れ替えた個数だけcが増加する
    x[b] = 0
    print(ans)

# for i in range(q):
#     count = 0
#     b, c = map(int, input().split())
#
#     for j in a:
#         if j == b:
#             a[count] = c
#         count += 1
#     a_list = [_ for _ in a]
#     ans.append(a_list)
#
# for answer in ans:
#     print(sum(answer))


### FIXED CODE ###

aa = input()

alpha = 'a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u,v,w,x,y,z'
alpha.split(',')

print('a' if aa in alpha else 'A')
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections
INF = 10**8

N, = map(int, sys.stdin.readline().rstrip().split(" "))
costs = map(int, sys.stdin.readline().rstrip().split(" "))


def solve(costs):
    dp = [0] + [INF for _ in costs]
    for i in range(len(costs)-2):
        dp[i+1] = min(dp[i+1], dp[i] + abs(costs[i+1] - costs[i]))
        dp[i+2] = min(dp[i+2], dp[i] + abs(costs[i+2] - costs[i]))
    #print(dp)
    return dp[-4]

ans = solve(costs + [INF] * 2)
assert ans < INF
print(ans)
exit(0)


### FIXED CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections
INF = 10**10

N, = map(int, sys.stdin.readline().rstrip().split(" "))
costs = map(int, sys.stdin.readline().rstrip().split(" "))


def solve(costs):
    dp = [0] + [INF for _ in costs]
    for i in range(len(costs)-2):
        dp[i+1] = min(dp[i+1], dp[i] + abs(costs[i+1] - costs[i]))
        dp[i+2] = min(dp[i+2], dp[i] + abs(costs[i+2] - costs[i]))
    #print(dp)
    return dp[-4]

ans = solve(costs + [INF] * 2)
assert ans < INF
print(ans)
exit(0)
s=input()
a=s.find("a")
z0=s.count("z")
for i in range (z0-1):
    s=s[:s.find("z")]+"a"+s[s.find("z")+1:]
    z=s.find("z")
print(z-a+1)
    

### FIXED CODE ###

s=input()
for i in range(len(s)):
    if s[i]=="A":
        a=i
        break
for j in range(len(s)):
    if s[-j-1]=="Z":
        z=(len(s)-j)
        break
print(z-a)
N,K = map(int,input().split())
A = list(map(int,input().split()))
town = [[] for _ in range(N)]
visited = [0]

for i in range(N):
  town[i] = [i,A[i] - 1]

def teleport(i,con):
  goal = town[i][1]
  if goal in visited or con == K:
    return goal
  else:
    visited.append(goal)
    return teleport(goal,con + 1)

l = teleport(visited[0],0)

if K < len(visited):
  print(visited[K] + 1)
else:
  if l in visited:
    cs = visited.index(l)
    cycle = visited[cs:]
    K = K - len(visited) + len(cycle)
  print(cycle[K % len(cycle)] + 1)
  


### FIXED CODE ###

N,K = map(int,input().split())

A = list(map(int,input().split()))
town = [[] for _ in range(N)]
visited = [0]
flag = [-1] * N

for i in range(N):
  town[i] = [i,A[i] - 1]

f = 0

while flag[f] == -1:
  t = town[f][1]
  flag[f] = t
  f = town[t][0]
  visited.append(t)
  
l = visited[-1]
lv = len(visited)

if K <= lv:
  print(visited[K] + 1)
else:
  cs = visited.index(l)
  cycle = visited[cs:-1]
  lc = len(cycle)
  print(cycle[(K - lv + 1) % lc] + 1)
##i
S = input()
answer = 0
for i in range(-int(-int(S))//2019):
    f = 2019 * i
    if f in S:
        answer += 1
        
print(answer)

### FIXED CODE ###

S = list(map(int, list(input())))

pops = 0
digi = 1
cnt = [0] * 2019
cnt[0] = 1

while S:
    s = S.pop()

    pops = (pops + s * digi) % 2019
    digi = (10 * digi) % 2019

    cnt[pops] += 1

ans = 0

for i in range(2019):
    ans += cnt[i] * (cnt[i] - 1) // 2

print(ans)
n,q = map(int,input().split())
tree = [[] for _ in range(n)]
point = [0] * n

for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    
for _ in range(q):
    a,b = map(int,input().split())
    point[a-1] += b
    
def dfs(now, prev = -1):
    for next in tree[now]:
        if next == prev:
            continue
        point[next] += point[now]
        
        dfs(next,now)
        
dfs(0)
print(*point)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
import sys
def input():
    return sys.stdin.readline()[:-1]

n,q = map(int,input().split())
tree = [[] for _ in range(n)]
point = [0] * n

for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    
for _ in range(q):
    a,b = map(int,input().split())
    a -= 1
    point[a] += b
    
def dfs(now, prev = -1):
    for next in tree[now]:
        if next == prev:
            continue
        point[next] += point[now]
        
        dfs(next, now)
        
dfs(0)
print(*point)
N,M=map(int,input().split())
a=[],b=[],c=[]
flag=0
for i in range(M):
    x,y=map(int,input().split())
    x.append(a)
    y.append(b)
    if x==1:
        c.append(y)
for i in range(M):
    if b[i]==N:
        if a[i] in c:
            flag+=1
if flag==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


### FIXED CODE ###

N,M=[int(i) for i in input().split()]
a=[]
b=[]
c=[]
for i in range(M):
    x,y=[int(i) for i in input().split()]
    if x==1 :
        c.append(y)
    if y==N:
        c.append(x)
if len(c)==len(set(c)):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
n,k = map(int,input()split())
d = []
for _ in range(n):
    d.append(list(map(int,input().split())))
d.sort(key=lambda x: x[0])
count = 0
for x,y in d:
    count += y
    if count >= k:
        break
print(x)

### FIXED CODE ###

n,k = map(int,input().split())
d = []
for _ in range(n):
    d.append(list(map(int,input().split())))
d.sort(key=lambda x: x[0])
count = 0
for x,y in d:
    count += y
    if count >= k:
        break
print(x)
A,B,K = list(map(int,input().split()))
for i in list(range(A,B+1))[:K] + list(range(A,B+1))[(-1*K):]:
    print(i)

### FIXED CODE ###

A,B,K = map(int,input().split())
for i in sorted(set(range(A,B+1)[:K])|set((range(A,B+1)[-1*K:]))):
    print(i)
s=input()

for e in s:
  if e="7":
    print("Yes")
    break
else:
  print("No")

### FIXED CODE ###

s=input()

for e in s:
  if e=="7":
    print("Yes")
    break
else:
  print("No")
n,k=map(int,input().split())
s=[]
d=[]
p=[]
t=[]
for i in range(n):
    a,b=map(int,input().split())
    p.append(b)
    if a not in s:
        s.append(a)
        d.append([b])
    else:
        d[s.index(a)].append(b)    
for i in range(len(s)):
    d[i].sort()
    t.append(d[i][-1])
t.sort()
p.sort()
r=[]
q=0
g=0
for i in range(k):
    if i<=len(t)+1:
        r.append(t[-1])
        q+=t[-1]
        g+=1
        p.pop(p.index(t[-1]))
        t.pop(-1)
    else:
        q+=sum(p[n-k+len(t):])
        del p[n-k+len(t):]
r.sort()
while r[0]+2*g-1<p[-1]:
    q+=p[-1]-r[0]
    g-=1
    p.pop(-1)
    r.pop(0)
print(g**2+q)

### FIXED CODE ###

n,k=map(int,input().split())
a=sorted([list(map(int,input().split()))for i in range(n)],key=lambda x:-x[1])
t=[0]*(n+1)
p,q=0,0
for i in a[:k]:
    p+=i[1]
    if t[i[0]]==0:
        q+=1
    t[i[0]]+=1
s=0
d=p+q*q
c=a[:k][::-1]
for i in a[k:]:
    if t[i[0]]==0:
        while s!=k:
            if t[c[s][0]]==1:
                s+=1
            else:
                break
        if s==k:
            break
        else:
            t[i[0]]+=1
            p-=c[s][1]-i[1]
            q+=1
            d=max(d,p+q*q)
            s+=1
print(d)
n = int(input())
l =[]
for i in range(1,n + 1):
    cnt = 0
    while i % 2 == 0 and i > 1:
        cnt += 1
        i = i / 2
        
            
    if cnt >= 1:
        l.append(int(i * 2 ** cnt))
print(max(l))
  

### FIXED CODE ###

n = int(input())
if n == 1:
    print(1)
elif n >= 2 and n < 4:
    print(2)
elif n >= 4 and n < 8:
    print(4)
elif n >= 8 and n < 16:
    print(8)
elif n >= 16 and n < 32:
    print(16)
elif n >= 32 and n < 64:
    print(32)
elif n >= 64:
    print(64)
N = int(input())
C = [0]

prev = -1
for _ in range(N):
    c = int(input())
    if c == prev:
        continue
    else:
        C.append(c)
        prev = c

MOD = 10**9+7
n = len(C)
dp = [0]*(n+1)
last = [-1]*(n+1)
dp[0] = 1
for i in range(1, n):
    if last[C[i]] == -1:
        last[C[i]] = i
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1]+dp[last[C[i]]]
        dp[i] %= MOD
        last[C[i]] = i
print(dp[-1])


### FIXED CODE ###

N = int(input())
C = [-1]

for _ in range(N):
    c = int(input())
    if c == C[-1]:
        continue
    else:
        C.append(c)

MOD = 10**9+7
dp = 1
prev = [0]*(max(C)+1)

for c in C[1:]:
    dp = (dp+prev[c]) % MOD
    prev[c] = dp
print(dp)
a,b = map(int,input().split)
x = a+b
if (x % 2 == 0):
  print(x/2)
else:
  print(x/2 + 1)

### FIXED CODE ###

a,b = map(int,input().split())
x = a+b
if (x % 2 == 0):
  print(int(x/2))
else:
  print(int(x/2 + 1))
p = [1, 0, 0, 0]

for s in input():
    if s == 'A' :
        p[1] += p[0]
    if s == 'B' :
        p[2] += p[1]
    if s == 'C' :
        p[3] += p[2]
    if s == '?':
        p[3] += p[2] + p[3] * 2
        p[2] += p[1] + p[2] * 2
        p[1] += p[0] + p[1] * 2
        p[0] += p[0] * 2
        
print(int(p[3] % (1e9 + 7)))

### FIXED CODE ###

p = [1, 0, 0, 0]
m = 1e9 + 7
def mod(x):
    return int(x % m)

for s in input():
    if s == 'A' :
        p[1] = mod(p[0] + p[1])
    if s == 'B' :
        p[2] = mod(p[1] + p[2])
    if s == 'C' :
        p[3] = mod(p[2] + p[3])
    if s == '?':
        p[3] = mod(p[2] + p[3] * 3)
        p[2] = mod(p[1] + p[2] * 3)
        p[1] = mod(p[0] + p[1] * 3)
        p[0] = mod(p[0] * 3)
        
print(int(p[3] % m))