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

import sys
input = sys.stdin.readline

def main():
    N,K = map(int,input().split())
     
    def modpow(a,n,mod):
        res = 1
        while n > 0:
            if n & 1:
                res = res * a % mod
            a = a * a % mod
            n >>= 1
        return res
     
    def modinv(a,mod):
        return modpow(a,mod - 2,mod)
     
    def cnk(a,b):
        MOD = 10**9+7
        ret = 1
        for i in range(b):
            ret *= (a-i)
            ret %= MOD
            ret = ret * modinv(i+1,MOD) % MOD
        return ret
     
     
    for i in range(1,K+1):
        if i == 1:
            print(N-K+1)
        else:
            print(cnk(N-K+1,i)*cnk(K-1,i-1)%(10**9+7))
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N,K = map(int,input().split())
     
    def modpow(a,n,mod):
        res = 1
        while n > 0:
            if n & 1:
                res = res * a % mod
            a = a * a % mod
            n >>= 1
        return res
     
    def modinv(a,mod):
        return modpow(a,mod - 2,mod)
     
    def cnk(a,b):
        MOD = 10**9+7
        ret = 1
        for i in range(b):
            ret *= (a-i)
            ret %= MOD
            ret = ret * modinv(i+1,MOD) % MOD
        return ret
     
     
    for i in range(1,K+1):
        if i > N - K +1:
            print(0)
        elif i == 1:
            print(N-K+1)
        else:
            print(cnk(N-K+1,i)*cnk(K-1,i-1)%(10**9+7))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()
T = input()
operation = 0
if len(S) == len(T):
    for i in range(len(S)):
        if S[i]!=T[i]:
            S.replace(S[i],T[i])
            operation+=1
    
print(operation)

### FIXED CODE ###

S,T,operation = input(), input(),0
for i in range(len(S)):
   if S[i]!=T[i]: operation+=1    
print(operation)
### BUGGY CODE ###

n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[0]*(z+2) for i in range(n-x+2)]for i in range(n+2)]
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)/(i+j+k)
print(dp[x][y][z])

### FIXED CODE ###

n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)
print(dp[x][y][z])
### BUGGY CODE ###


q = int(input())
query = [list(map(int,input().split())) for _ in range(q)]

N = int(1e+5)
max_num = int(N**0.5)
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2,max_num+1):
    if not is_prime[i]:
        continue
    for j in range(i*2,N+1,i):
        is_prime[j] = False

ans = [False] * (N+1)
for i in range(3,N+1,2):
    b = (i+1)//2
    if is_prime[i] and is_prime[b]:
        ans[i] = True

for l,r in query:
    print(ans[l:r+1].count(True))

### FIXED CODE ###


q = int(input())
query = [list(map(int,input().split())) for _ in range(q)]

N = int(1e+5)
max_num = int(N**0.5)
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2,max_num+1):
    if not is_prime[i]:
        continue
    for j in range(i*2,N+1,i):
        is_prime[j] = False

ans = [False] * (N+1)
for i in range(3,N+1,2):
    b = (i+1)//2
    if is_prime[i] and is_prime[b]:
        ans[i] = True

comurative_ans = [0] * (N+1)
sum_true = 0
for i in range(N+1):
    if ans[i] :
        sum_true += 1
    comurative_ans[i] = sum_true
for l,r in query:
    print(comurative_ans[r+1]-comurative_ans[l-1])
### BUGGY CODE ###

import sys
stdin = sys.stdin
def li(): return map(int, stdin.readline().split())
N = li()
A = list(li())

def gcd(A, B):
    # fast return
    if B == 1 or A == 1:
        return 1

    # normal gcd logic
    while B not in (1, 0):
        A, B = min(A, B), abs(A - B)
    if B == 0:
        return A
    elif B == 1:
        return 1

A = list(filter(lambda x:x>0, A))
A.sort()
if len(A) == 0:
    print(0)
else:
    res = A[0]
    for a in A:
        res = gcd(a, res)
        if res == 1:
            break

    print(res)


### FIXED CODE ###

import sys
stdin = sys.stdin
def li(): return map(int, stdin.readline().split())
N = li()
A = list(li())

def gcd(A, B):

    # normal gcd logic
    while B not in (1, 0):
        A, B = (A, B) if A > B else (B, A)
        _, mod = divmod(A, B)
        A, B = B, mod
    if B == 0:
        return A
    elif B == 1:
        return 1

A = list(filter(lambda x:x>0, A))
A.sort()
if len(A) == 0:
    print(0)
else:
    res = A[0]
    for a in A:
        res = gcd(a, res)
        if res == 1:
            break

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

N, K = map(int, input().split())
pi = list(map(int, input().split()))
index = []
for i in range(N-K+1):
    x = sum(pi[i:i+K])
    index.append(x)
max_index = index.index(max(index))
EX_max = 0
for i in range(max_index, max_index+K):
  EX_max += 1+(pi[i]-1)*0.5
print(EX_max)

### FIXED CODE ###

N, K = map(int, input().split())
pi = list(map(int,input().split()))
def EV(x):
    return 1+(x-1)*0.5
for i in range(N):
    pi[i] = EV(pi[i])

ruisekiwa = sum(pi[0:K])
max_EV = ruisekiwa

for i in range(N-K):
    ruisekiwa = ruisekiwa + pi[i+K]-pi[i]
    if ruisekiwa > max_EV:
        max_EV = ruisekiwa
print(max_EV)
### BUGGY CODE ###

s = input()
q = int(input())
querys = [list(map(str,input().split())) for _ in range(q)]

direction = 0
mae = ""
ato = ""

for i,query in enumerate(querys):
    if query[0] == "1":
        direction = (direction+1)%2
    else:
        if (int(query[1])-1 + direction)%2 == 0:
            mae += query[2]
        else:
            ato += query[2]


s = mae[::-1] + s
s = s + ato

if direction == 1:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

s = input()
q = int(input())
querys = [list(map(str,input().split())) for _ in range(q)]

direction = 0
mae = ""
ato = ""

for i,query in enumerate(querys):
    if query[0] == "1":
        direction = (direction+1)%2
    else:
        if (int(query[1])-1 + direction)%2 == 0:
            mae += query[2]
        else:
            ato += query[2]

s = mae[::-1] + s
s = s + ato

if direction == 1:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False
prime2017 = [0] * 100000
prime2017[0] = 0
prime2017[1] = 0
prime2017[2] = 0
for x in range(3,len(prime)):
    if prime[x] and prime[int((x+1)/2)]:
        prime2017[x] = 1
q=int(input())
lr_ary = []
for _ in range(q):
    l,r=list(map(int, input().split()))
    ret=sum(prime2017[x] for x in range(l,r+1,2))
    print(ret)

### FIXED CODE ###

from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False
prime2017 = [0] * 100000
prime2017[0] = 0
prime2017[1] = 0
prime2017[2] = 0
ruiseki=0
for x in range(3,len(prime)):
    if prime[x] and prime[int((x+1)/2)]:
        ruiseki+=1
    prime2017[x] = ruiseki
q=int(input())
lr_ary = []
for _ in range(q):
    l,r=list(map(int, input().split()))
    print(prime2017[r]-prime2017[l-1])
### BUGGY CODE ###

n = int(input())
ss = input()

queue = []
for i in range(n-2):
    queue.append(('', i))

ans = 0
nn = n-3
memo = set()
while queue:
    s, pos = queue.pop()
    for i in range(n-2):
        if pos + i >= n:
            continue
        t = s + ss[pos+i]
        if len(t) == n - nn:
            memo.add(t)
        else:
            queue.append((t,pos+i+1))
print(len(memo))
# print(memo)


### FIXED CODE ###

from collections import Counter
from bisect import bisect_right

n = int(input())
s = input()
ndict = {str(i):[] for i in range(10)}
for i,c in enumerate(s):
    ndict[c].append(i)

ans = 0
for i in range(1000):
    PIN = str(i).zfill(3)
    idx = -1
    cc = ''
    for c in PIN:
        if ndict[c] == []:
            break
        tmp = bisect_right(ndict[c], idx)
        if tmp >= len(ndict[c]):
            break
        idx = ndict[c][tmp]
        cc = c
    else:        
        ans += 1
print(ans)
### BUGGY CODE ###

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

# 距離間リスト
d_li = []
for i in range(N-1):
	d_li.append(A_li[i+1]-A_li[i])

d_li.append(K+A_li[0] - A_li[N-1])

ans = float('inf')
for d in d_li:
	ans = min(ans,sum(d_li)-d)

print(ans)

### FIXED CODE ###

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

# 距離間リスト
d_li = []
for i in range(N-1):
	d_li.append(A_li[i+1]-A_li[i])

d_li.append(K+A_li[0] - A_li[N-1])


allsum = sum(d_li)
ans = allsum
for d in d_li:
	ans = min(ans,allsum-d)

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

import math


a, b, x = map(int, input().split())
eps = 10 ** -6
r = 90 * 10 ** 6
h1 = x / a ** 2
if h1 >= b / 2:
    for e in range(0, r):
        th = e * eps * (math.pi / 180)
        c = b - h1 - (a / 2 * math.tan(th))
        if c <= 0:
            break
    print(e * eps)
else:
    h2 = x / (a * b)
    for e in range(0, r):
        th = e * eps * (math.pi / 180)
        c = 2 * h2 - (b * math.tan(th))
        if c <= 0:
            break
    print(90 - e * eps)

### FIXED CODE ###

import math


a, b, x = map(int, input().split())
r = 180 / math.pi
h = x / a ** 2
c = h * 2 - b
d = 2 * x / (a * b)
if h >= b / 2:
    th = math.atan((h - c) / (a / 2)) * r
else:
    th = ((math.pi / 2) - math.atan((d / b))) * r
print(th)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
xli = na()
li = []
ans = 1000000000
for i in range(n - k + 1):
    t = xli[i:i + k]
    if t[0] * t[-1] < 0:
        ans = min(ans, 2 * abs(t[0]) + abs(t[-1]), abs(t[0]) + 2 * abs(t[-1]))
    else:
        if t[0] <= 0:
            ans = min(ans, abs(t[0]))
        else:
            ans = min(ans, abs(t[-1]))
print(ans)

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
xli = na()
li = []
ans = 1000000000
idx = -1
for i in range(n):
    if xli[i] > 0:
        idx = i
        break
if idx == -1:
    print(abs(xli[-k]))
elif idx == 0:
    print(abs(xli[k-1]))
else:
    for i in range(max(idx - k, 0), min(idx+1, n-k+1)):
        if xli[i] * xli[i + k -1] < 0:
            ans = min(ans, 2 * abs(xli[i]) + xli[i + k -1], abs(xli[i]) + 2 * xli[i + k -1])
        else:
            if xli[i + k -1] <= 0:
                ans = min(ans, abs(xli[i]))
            else:
                ans = min(ans, abs(xli[i + k -1]))
    print(ans)
### BUGGY CODE ###

from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n,k = map(int,input().split())

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

    #ループを探す？

    checked_list = [1]
    que = deque([a[0]])

    counter = 0
    q_append = que.append

    while True:
        counter += 1
        x = que.popleft()
        if counter == k:
            print(x)
            exit()
        if x in checked_list:
            startflg = checked_list.index(x)
            loop_length = counter - startflg
            loop_list = checked_list[startflg:counter]
            amari = (k-startflg) % loop_length
            print(loop_list[amari])
            exit()
        else:
            q_append(a[x-1])
            checked_list.append(x)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n,k = map(int,input().split())

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

    #ループを探す？

    checked_dict = {1:0}
    que = deque([a[0]])

    counter = 0


    while True:
        counter += 1
        x = que.popleft()
        if counter == k:
            print(x)
            exit()
        if x in checked_dict:
            startflg = checked_dict[x]
            loop_length = counter - startflg

            inverse_dict = {v:k for k,v in checked_dict.items()}

            loop_list = [inverse_dict[i] for i in range(startflg,startflg+loop_length)]
            amari = (k-startflg) % loop_length
            print(loop_list[amari])
            exit()
        else:
            que.append(a[x-1])
            checked_dict[x] = counter

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

N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in range(N):
    target = arr[i]
    if tmp[target] >= 2:
        continue
    flg = True
    for k in range(1,int(target**0.5)+1):
        if target % k == 0:
            if tmp[k] != 0 and target != k:
                flg = False
                break
            if k != target // k:
                if tmp[target // k] != 0 and target // k != target:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ma = max(arr)
check = [True]*(ma+1)
cnt = [0]*(ma+1)
for i in arr:
    cnt[i] += 1
ans = 0
for i in arr:
    if not check[i]:
        continue
    for k in range(i,ma+1,i):
        check[k] = False
    if cnt[i] <= 1:
        ans += 1
print(ans)
### BUGGY CODE ###

s=input()
cnt=0
f1=False
f2=False
while(1):
  f1=False
  f2=False
  x1=s.find('10')
  if x1==-1:
    f1=True
  x2=s.find('01')
  if x2==-1:
    f2=True
  if f1 and f2:
    break
  elif f1:
    x=x2
  elif f2:
    x=x1
  else:
    x=min(x1,x2)
  s=s[:x]+s[x+2:]
  cnt+=1
print(cnt*2)

### FIXED CODE ###

s=input()
cnt=0
idx=0
while(1):
  if idx >=len(s):
    break
  if s[idx:idx+2] in ('01','10'):
    cnt+=1
    s=s[:idx]+s[idx+2:]
    idx = max(0,idx-1)
  else:
    idx+=1
print(cnt*2)
### BUGGY CODE ###

n = int(input())
s = list(map(int, input()))

a = [[set() for j in range(10)] for i in range(10)]
for i in range(1, len(s) - 1):
    t = s[i]
    l = set(s[i+1:])
    for j in set(s[:i]):
        a[t][j] |= l

ans = 0
for b in a:
    for c in b:
        ans += len(c)
print(ans)

### FIXED CODE ###

n = int(input())
s = list(map(int, input()))

rr = {}
r = set()
for i in range(len(s) - 1, 0, -1):
    t = s[i]
    r.add(t)
    rr[i] = r.copy()

a = [[set() for j in range(10)] for i in range(10)]
l = set()
for i in range(1, len(s) - 1):
    t = s[i]
    l.add(s[i-1])
    r = rr[i+1]
    for j in l:
        a[t][j] |= r

ans = 0
for b in a:
    for c in b:
        ans += len(c)
print(ans)
### BUGGY CODE ###

import numpy as np

def update(A, N):
    B = [0] * N
    for i in range(0, N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        B[l] += 1
        if (r + 1 < N):
            B[r + 1] -= 1
    return np.cumsum(B)

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(0, min(42, K)):
        A = update(A, N)
    print(" ".join([str(item) for item in A]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

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

sum_a=sum(alist)
alist.sort()
#print(sum_a,alist)

#M=1の場合にも対応
divisor_set=set()
for i in range(1,int(sum_a**0.5)+1):
  if sum_a%i==0:
    divisor_set.add(i)
    divisor_set.add(sum_a//i)
divisor_list=list(divisor_set)
divisor_list.sort()
#print(divisor_list)

answer=0
for d in divisor_list:
  rlist=[]
  for a in alist:
    rlist.append((a%d,(d-a%d)%d))
  rlist.sort()
  
  r1list,r2list=[],[]
  for r1,r2 in rlist:
    r1list.append(r1)
    r2list.append(r2)  
  #print(d,r1list,r2list)
  
  for i in range(len(rlist)):
    r1sum=sum(r1list[:i])
    r2sum=sum(r2list[i:])
    if r1sum==r2sum and r1sum<=K:
      answer=d
      break
      
print(answer)

### FIXED CODE ###

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

sum_a=sum(alist)
alist.sort()
#print(sum_a,alist)

#M=1の場合にも対応
divisor_set=set()
for i in range(1,int(sum_a**0.5)+1):
  if sum_a%i==0:
    divisor_set.add(i)
    divisor_set.add(sum_a//i)
divisor_list=list(divisor_set)
divisor_list.sort()
#print(divisor_list)

answer=0
for d in divisor_list:
  rlist=[]
  for a in alist:
    rlist.append((a%d,(d-a%d)%d))
  rlist.sort()
  
  r1list,r2list=[],[]
  for r1,r2 in rlist:
    r1list.append(r1)
    r2list.append(r2)  
  #print(d,r1list,r2list)
  
  for i in range(len(rlist)):
    r1sum=sum(r1list[:i])
    r2sum=sum(r2list[i:])
    if r1sum==r2sum and r1sum<=K:
      answer=d
      break
      
print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    MOD = 998244353

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[i] += data[iB]
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(iFr, iTo):
        return getSum(iTo) - getSum(iFr-1)


    N, K = map(int, input().split())
    LRs = [tuple(map(int, input().split())) for _ in range(K)]

    data, numPow2 = makeBIT(N)

    addValue(0, 1)

    for i in range(1, N):
        v = 0
        for L, R in LRs:
            x, y = i-R, i-L
            if y < 0:
                continue
            if x < 0:
                x = 0
            v += getRangeSum(x, y) % MOD
            v %= MOD
        addValue(i, v)

    ans = getRangeSum(N-1, N-1) % MOD
    print(ans)


solve()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    MOD = 998244353

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[i] += data[iB]
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(iFr, iTo):
        return getSum(iTo) - getSum(iFr-1)


    N, K = map(int, input().split())
    LRs = [tuple(map(int, input().split())) for _ in range(K)]

    data, numPow2 = makeBIT(N)

    addValue(0, 1)

    for i in range(1, N):
        v = 0
        for L, R in LRs:
            x, y = i-R, i-L
            if y < 0:
                continue
            if x < 0:
                x = 0
            v += getRangeSum(x, y) % MOD
            v %= MOD
        addValue(i, v)

    ans = getRangeSum(N-1, N-1) % MOD
    print(ans)


solve()
### BUGGY CODE ###

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

f=True
for Ti in T:
    if D.count(Ti)<T.count(Ti):
        f=False
        break

print('YES' if f else 'NO')

### FIXED CODE ###

from collections import Counter

N=int(input())
D=list(map(int,input().split()))
CD=Counter(D)
# print(CD) #DB
M=int(input())
T=list(map(int,input().split()))
CT=Counter(T)
# print(CT) #DB

f=True
for Ti in CT.keys():
    if CD[Ti]<CT[Ti]:
        f=False
        break

print('YES' if f else 'NO')
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
B = [0]*Q
C = [0]*Q

sum = np.sum(A)

for i in range(Q):
    B[i], C[i] = map(int, input().split())
    
    time = 0
    A = np.sort(A)
    for k in range(N):
        if A[k] == B[i]:
            A[k] = C[i]
            time += 1
        elif A[k] > B[i]:
            break
        
    sum += (C[i]-B[i])*time

    print(sum)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q

num = [0]*100000

for i in range(N):
    num[A[i]-1] += 1

sum = sum(A)

for i in range(Q):
    B[i], C[i] = map(int, input().split())
    
    sum += (C[i]-B[i])*num[B[i]-1]
    num[C[i]-1] += num[B[i]-1] 
    num[B[i]-1] = 0

    print(sum)
### BUGGY CODE ###

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

res = 0

for i in range(N):
    tmp_res = 0
    num = i
    if num < N-1:
        while H_list[num] >= H_list[num+1]:
            num += 1
            tmp_res += 1
            if num >= N-1:
                break
    
    if res < tmp_res:
        res = tmp_res

print(res)


### FIXED CODE ###

import numpy as np


N = int(input())
A = np.array(input().split(), dtype=np.int32)

left_idx = np.arange(N)
# 自身が左以下ならば0に
left_idx[1:][A[:-1] >= A[1:]] = 0
np.maximum.accumulate(left_idx, out=left_idx)

answer = (np.arange(N) - left_idx).max()
print(answer)
### BUGGY CODE ###

S = input()
dp0 = 1
dp1 = 0
dp2 = 0
dp3 = 0

for s in S:
    tmp0 = 0
    tmp1 = 0
    tmp2 = 0
    tmp3 = 0
    
    if s == 'A' or s == '?':
        tmp0 += dp0
        tmp1 += dp1
        tmp2 += dp2
        tmp3 += dp3
        tmp1 += dp0
    if s == 'B' or s == '?':
        tmp0 += dp0
        tmp1 += dp1
        tmp2 += dp2
        tmp3 += dp3
        tmp2 += dp1
    if s == 'C' or s == '?':
        tmp0 += dp0
        tmp1 += dp1
        tmp2 += dp2
        tmp3 += dp3
        tmp3 += dp2
    dp0 = tmp0
    dp1 = tmp1
    dp2 = tmp2
    dp3 = tmp3
    
print(dp3%(10**9+7))

### FIXED CODE ###

def main():
    S = input()
    mod = 10**9+7
    dp0 = 1
    dp1 = 0
    dp2 = 0
    dp3 = 0

    for s in S:
        tmp0 = dp0
        tmp1 = dp1
        tmp2 = dp2
        tmp3 = dp3

        if s == '?':
            tmp0 += 2*dp0 % mod
            tmp1 += (2*dp1 + dp0) % mod
            tmp2 += (2*dp2 + dp1) % mod
            tmp3 += (2*dp3 + dp2) % mod
        elif s == 'A':
            tmp1 += dp0 % mod
        elif s == 'B':
            tmp2 += dp1 % mod
        elif s == 'C':
            tmp3 += dp2 % mod
        dp0 = tmp0
        dp1 = tmp1
        dp2 = tmp2
        dp3 = tmp3

    print(dp3%(mod))
if __name__ == '__main__':
    main()