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

N = int(input())
P = [int(i) for i in input().split()]
ans = {}
for i in range(N):
    flag = 0
    try:
        i_min = min(P[:i])
    except:
        ans[i] = 0
        continue
    if P[i] <= i_min:
        #print(P[i], i_max)
        ans[i] = 0
    
    #if not flag:
    #    ans += 1
#print(ans.keys())
print(len(ans.keys()))

### FIXED CODE ###

N = int(input())
P = [int(i) for i in input().split()]
min_ = 9999999999
ans = 0
for i in range(N):
    
    min_ = min(P[i], min_)

        
    if P[i] == min_:
        #print(P[i], i_max)
        ans += 1
    
    #if not flag:
    #    ans += 1
#print(ans.keys())
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())

grid = [[] for h in range(H)]

for h in range(H):
    grid[h] = list(input())

L = [[0] * W for h in range(H)]
U = [[0] * W for h in range(H)]
R = [[0] * W for h in range(H)]
D = [[0] * W for h in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            L[h][w] = 0
            U[h][w] = 0
        else:
            if w == 0:
                L[h][w] = 1
            else:
                L[h][w] = L[h][w - 1] + 1
            if h == 0:
                U[h][w] = 1
            else:
                U[h][w] = U[h - 1][w] + 1

        if grid[H - h - 1][W - w - 1] == '#':
            R[H - h - 1][W - w - 1] = 0
            D[H - h - 1][W - w - 1] = 0
        else:
            if w == 0:
                R[H - h - 1][W - w - 1] = 1
            else:
                R[H - h - 1][W - w - 1] = R[H - h - 1][W - w] + 1
            if h == 0:
                D[H - h - 1][W - w - 1] = 1
            else:
                D[H - h - 1][W - w - 1] = D[H - h][W - w - 1] + 1
            


import numpy as np
print(max((np.array(L) + np.array(R) + np.array(U) + np.array(D) - 3).ravel()))

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'

D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)

for h in range(H):
    U[h] = (U[h - 1] + 1) * S[h]
    D[-h - 1] = (D[-h] + 1) * S[-h - 1]
for w in range(W):
    L[:, w] = (L[:, w - 1] + 1) * S[:, w]
    R[:, -w - 1] = (R[:, -w] + 1) * S[:, -w - 1]
print(np.max(U + D + L + R) - 3)
### BUGGY CODE ###

n = int(input())
S = 0
for i in range(1,n+1):
  a = n//i
  j = i * a
  s = (i+j)*a//2
  S += s
  
print(S)  
  

### FIXED CODE ###

n = int(input())
S = 0
for i in range(1,n+1):
  a = n//i
  j = i * a
  s = (i+j)*a//2
  S += s
  
print(S)
### BUGGY CODE ###

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

for i in range(n):
    tmp = abs(sum(a[:i])-sum(a[i:]))
    ans = tmp if i==0 else min(ans, tmp)

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
t = sum(a)
b = 0

for i in range(n):
    b += a[i]
    tmp = abs(2*b-t)
    ans = tmp if i==0 else min(ans, tmp)

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

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([-1 if i =="." else -2 for i in s])

dq = deque()
dq.append((Ch,Cw))
S[Ch][Cw]=0

while dq:
  a=dq.pop()
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and abs(i-2)+abs(j-2)==1 and (S[a[0]-2+i][a[1]-2+j]==-1 or S[a[0]-2+i][a[1]-2+j]>S[a[0]][a[1]]):
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]
        dq.appendleft((a[0]-2+i,a[1]-2+j))
      elif a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and (S[a[0]-2+i][a[1]-2+j]==-1 or S[a[0]-2+i][a[1]-2+j]>S[a[0]][a[1]]+1):
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]+1
        dq.append((a[0]-2+i,a[1]-2+j))

print(S[Dh][Dw])

### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([10**10 if i =="." else -1 for i in s])
visit=[[False for i in range(W)] for j in range(H)]

dq = deque()
dq.append((Ch,Cw,0))
S[Ch][Cw]=0
counter=0

while dq:
  a=dq.popleft()
  if visit[a[0]][a[1]]==True:
    continue
  elif S[a[0]][a[1]]==counter:
    visit[a[0]][a[1]]=True
  elif a[2]==counter+1:
    visit[a[0]][a[1]]=True
    counter+=1
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W:
        if abs(i-2)+abs(j-2)==1 and S[a[0]][a[1]]<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter
          dq.appendleft((a[0]-2+i,a[1]-2+j,counter))
        elif S[a[0]][a[1]]+1<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter+1
          dq.append((a[0]-2+i,a[1]-2+j,counter+1))
  #print(visit,counter,a,dq,"\n")
if S[Dh][Dw]==10**10:
  print(-1)
else:
  print(S[Dh][Dw])
### BUGGY CODE ###

import numpy as np

n, m = [int(i) for i in input().split()]
to_i = dict(AC=1, WA=0)
ps = list()
ss = list()
for i in range(m):
  p, s = input().split()
  ps.append(int(p))
  ss.append(to_i[s])
ps = np.array(ps)
ss = np.array(ss)

sub_ps = np.unique(ps)

cnt_c, cnt_w = 0, 0
for sp in sub_ps:
  indices = np.where(ps==sp)[0]
  s_sp = ss[indices]
  if s_sp.sum() == 0:
    continue
  num_ws = np.where(s_sp == 1)[0][0]
  cnt_w += num_ws
  cnt_c += 1

print(cnt_c, cnt_w)

### FIXED CODE ###

n, m = [int(i) for i in input().split()]
ans = [input().split() for _ in range(m)]

is_ac = [0 for i in range(n)]
cnt_wa = [0 for i in range(n)]
for p, s in ans:
  p = int(p) - 1
  if is_ac[p]:
    continue
  if s == 'AC':
    is_ac[p] = 1
  else:
    cnt_wa[p] += 1

cor = sum(is_ac)
pena = 0
for p, c in enumerate(is_ac):
  if c:
    pena += cnt_wa[p]

print(cor, pena)
### BUGGY CODE ###

A, B = map(int, input().split())
X = [format(i, "b") for i in range(A, B+1)]
ans = [0 for i in range(len(X[-1]))]
for i in range(len(X)):
    while len(X[i]) != len(X[-1]):
        X[i] = "0" + X[i]

for x in X:
    for j in range(len(x)):
        ans[j] = ans[j] + int(x[j])
        if ans[j] % 2 == 0:
            ans[j] = 0

for i in range(len(ans)):
    ans[i] = str(ans[i])

ans = "".join(ans)
ans = int(ans, 2)
print(ans)


### FIXED CODE ###

def oddsolve(x):
    return int((x+1) / 2 % 2)
def solve(x):
    if x % 2 ==0:
        return oddsolve(x+1)^(x+1)
    else:
        return oddsolve(x)

A, B = map(int,input().split())

print(solve(A-1) ^ solve(B))
### BUGGY CODE ###

from bisect import bisect_left
H, W = map(int, input().split())
s = [input() for i in range(H)]

def length(index, block_idx, full_length):
    if len(block_idx) == 0:
        return full_length
    idx = bisect_left(block_idx, index)
    if idx == len(block_idx):
        return full_length - index
    return block_idx[idx] - index

rows = []

for i in range(H):
    row = []
    block_idx = []
    for k in range(len(s[i])):
        if s[i][k] == "#":
            block_idx.append(k)

    for j in range(W):
        if j == 0:
            if s[i][0] == "#":
                row.append(0)
            else:
                l = length(0, block_idx, W)
                row.append(l)
        else:
            if s[i][j] == "#":
                row.append(0)
            else:
                if s[i][j-1] != "#":
                    row.append(row[len(row)-1])
                else:
                    l = length(j, block_idx, W)
                    row.append(l)
    rows.append(row)

columns = []

for i in range(W):
    column = []

    _s = ""
    block_idx = []
    for k in range(H):
        _s += s[k][i]
        if s[k][i] == "#":
            block_idx.append(k)

    for j in range(H):
        if j == 0:
            if _s[0] == "#":
                column.append(0)
            else:
                l = length(0, block_idx, H)
                column.append(l)
        else:
            if _s[j] == "#":
                column.append(0)
            else:
                if _s[j - 1] != "#":
                    column.append(column[len(column) - 1])
                else:
                    l = length(j, block_idx, H)
                    column.append(l)
    columns.append(column)

res = []
for i in range(H):
    for j in range(W):
        r = rows[i][j]
        c = columns[j][i]
        res.append(r+c-1)
print(max(res))

### FIXED CODE ###


H, W = map(int, input().split())
s = [input() for i in range(H)]

l = [[0 for i in range(W)] for j in range(H)]
r = [[0 for i in range(W)] for j in range(H)]
d = [[0 for i in range(W)] for j in range(H)]
u = [[0 for i in range(W)] for j in range(H)]

# Up-Light
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            l[i][j] = 0
            u[i][j] = 0
            continue

        if j == 0:
            l[i][j] = 1
        else:
            l[i][j] = l[i][j-1] + 1

        if i == 0:
            u[i][j] = 1
        else:
            u[i][j] = u[i-1][j] + 1

# Right-Down
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if s[i][j] == "#":
            r[i][j] = 0
            d[i][j] = 0
            continue

        if j == W-1:
            r[i][j] = 1
        else:
            r[i][j] = r[i][j+1] + 1

        if i == H-1:
            d[i][j] = 1
        else:
            d[i][j] = d[i+1][j] + 1

max_score = 0
for i in range(H):
    for j in range(W):
        score = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        if score > max_score:
            max_score = score
print(max_score)
### BUGGY CODE ###

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

max_n = max(max(A),1)
cnt = [0]*max_n
for i in range(max_n):
    for a in A:
        if abs(a-i)<=1:
            cnt[i] += 1
print(max(cnt))

### FIXED CODE ###

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

cnt = [0]*(10**5+2)
for a in A:
    cnt[a] += 1
ans = []
for a in A:
    if a == 0:
        ans.append(cnt[a] +cnt[a+1])
    else:
        ans.append(cnt[a-1] + cnt[a] +cnt[a+1])
print(max(ans))
### BUGGY CODE ###

import itertools


h, w = map(int, input().split())
c = [list(map(ord, input())) for i in range(h)]
c = list(itertools.chain.from_iterable(c))
INF = 10 ** 9


ans = 0
dq = [0] * ((h + 1) ** 2)
for wi in range(w - 1):
    for diff in range(h + 1):
        cnt = 0
        for i in range(h - diff):
            cnt += (c[i * w + wi] == c[(i + diff) * w + wi + 1])
        dq[diff * (h + 1)] = cnt
        for i in range(h - diff - 1):
            cnt -= (c[(h - i - 1 - diff) * w + wi] == c[(h - i - 1) * w + wi + 1])
            dq[(i + 1 + diff) * (h + 1) + i + 1] = cnt

        cnt = 0
        for i in range(h - diff):
            cnt += (c[(i + diff) * w + wi] == c[i * w + wi + 1])
        dq[diff] = cnt
        for i in range(h - diff - 1):
            cnt -= (c[(h - i - 1 - diff) * w + wi + 1] == c[(h - i - 1) * w + wi])
            dq[(i + 1) * (h + 1) + i + 1 + diff] = cnt
            
    dp = [INF] * ((h + 1) ** 2)
    dp[0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[(i + 1) * (h + 1) + j] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[(i + 1) *(h + 1) + j])
            if j + 1 < h + 1:
                dp[i * (h + 1) + j + 1] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[i * (h + 1) + j + 1])
    ans += dp[-1]

print(ans)
    

### FIXED CODE ###

def solve(k):
    dp = [[0] * (h + 1) for i in range(h + 1)]
    for i in range(h):
        for diff in range(h - i):
            dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
            dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])

    dq = [[INF] * (h + 1) for i in range(h + 1)]
    dq[0][0] = 0
    for i in range(h):
        dq[i + 1][0] = dq[i][0] + dp[h - i][h]
        dq[0][i + 1] = dq[0][i] + dp[h][h - i]  
    for i in range(h):
        for j in range(h):
            dq[i + 1][j + 1] = min(dq[i + 1][j] + dp[h - (i + 1)][h - j],
                                   dq[i][j + 1] + dp[h - i][h - (j + 1)])

    return dq[h][h]


h, w = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 5
OFFSET = 500

ans = 0
for i in range(w - 1):
    ans += solve(i)
    
print(ans)
### BUGGY CODE ###

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

l1=[]
l2=[]

for i in range(n):
    if i%2==1:
        l1.append(l[i])
    else:
        l2.append(l[i])

ans=len(l1)+len(l2)

l1cnt=0
l1cnt2=0
l1ind=0


for i in set(l1):
    cnt = l1.count(i)
    if cnt>l1cnt:
        l1ind=i
        l1cnt=cnt
    elif cnt>l1cnt2:
        l1cnt2=cnt

l2cnt=0
l2cnt2=0
l2ind=0

for i in set(l2):
    cnt = l2.count(i)
    if cnt>l2cnt:
        l2ind=i
        l2cnt=cnt
    elif cnt>l2cnt2:
        l2cnt2=cnt

if l1ind!=l2ind:
    ans -= l1cnt + l2cnt
else:
    ans -= max(l1cnt+l2cnt2,l1cnt2+l2cnt)

print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
v = list(map(int,input().split()))
v_even,v_odd =[[],[]]

for i in range(n//2):
    v_even.append(v[2*i])
    v_odd.append(v[2*i+1])

mc1 = Counter(v_even).most_common()
mc2 = Counter(v_odd).most_common()

k1,v1 = mc1[0]
k2,v2 = mc2[0]

if k1!=k2:
    print(n-v1-v2)
else:
    w1=0
    if len(mc1)>1:
        w1=mc1[1][1]
    w2=0
    if len(mc2)>1:
        w2=mc2[1][1]
    print(n-max(v1+w2,v2+w1))
### BUGGY CODE ###

from heapq import heapify, heappush, heappop


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


numbers = []
heapify(numbers)
for a in lst_A:
    heappush(numbers, -a)
for _ in range(M):
    b, c = map(int, input().split())
    for _ in range(b):
        heappush(numbers, -c)


ans = -sum(heappop(numbers) for _ in range(N))
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_BC = [list(map(int, input().split())) for _ in range(M)]


lst_A.sort()
lst_BC.sort(key=lambda x:-x[1])


lst_D = []
add_num = N
for b, c in lst_BC:
    lst_D += [c] * min(b, N - len(lst_D))
lst_D = lst_D + [0] * (N - len(lst_D))


for i in range(N):
    if lst_A[i] >= lst_D[i]:
        break
    lst_A[i] = lst_D[i]


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

n,a,b = [int(x) for x in input().rstrip().split()]
l=[]
n1=1
st=1
ans=0
for i in range(1,n+1):
    n1=n1*(n-i+1)
    st=st*i
    ans1 = (n1//st)
    if i==a or i==b:
        l.append(n1//st)
        continue
    else:
        if n<(i/2):
            ans+=l[n-i]
        else:
            ans+=ans1
            l.append(ans1)

print(ans%(10**9+7))

### FIXED CODE ###

mod=10**9+7
n,a,b=[int(x) for x in input().rstrip().split()]

def modpow(a,n):
  if n<1:
    return 1
  ans=modpow(a,n//2)
  ans=(ans*ans)%mod
  if n%2==1:
    ans*=a
  return ans%mod

def conb(n,i):
  inv,ans=1,1
  for j in range(1,i+1):
    ans=ans*(n-j+1)%mod
    inv=inv*j%mod
  return (ans*modpow(inv,mod-2))%mod

ans_n=pow(2,n,mod)-1
ans_a=conb(n,a)
ans_b=conb(n,b)

print((ans_n-ans_a-ans_b)%mod)
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

N = int(input())
S = input()
q = collections.deque()
pm = itertools.combinations(range(N),3)

for i in pm:
    s = S[i[0]]+S[i[1]]+S[i[2]]
    q.append(s)
print(len(set(q)))


### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

N = int(input())
S = input()
sl = list(S)
setS = set(S)
ans = 0
for i in range(10):
    if str(i) not in setS:
        continue
    else:
        i100_ind = sl.index(str(i))
        S10 =sl[i100_ind+1:-1]
        S10set = set(S10)
        for j in range(10):
            if str(j) not in S10set:
                continue
            else:
                i10_ind = S10.index(str(j))
                S1 = S10[i10_ind+1:]
                S1.append(sl[-1])
                ans += len(set(S1))
print(ans)
### BUGGY CODE ###

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

count = 1
for i in range(1, N):
    if min(P[:i]) >= P[i]:
        count += 1
print(count)

### FIXED CODE ###

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

count = 1
minimum = P[0]
for i in range(1, N):
    minimum = min(P[i-1], minimum)
    if P[i] <= minimum:
        count += 1
print(count)
### BUGGY CODE ###

A,B,C,K = map(int,input().split())

ans = 0

while K > 0 and A > 0:
    ans += 1
    A -= 1
    K -= 1
    
while K > 0 and B > 0:
    ans += 0
    B -= 1
    K -= 1

while K > 0 and C > 0:
    ans += -1
    C -= 1
    K -= 1
    
print(ans)
    
    
  
  

### FIXED CODE ###

A,B,C,K = map(int,input().split())


if K-A <=0:
  ans = K

elif K-A-B<=0:
  ans = A

elif K-A-B-C<=0:
  ans = A-(K-A-B)
  
print(ans)
### BUGGY CODE ###

list_len = int(input())
integer_list = tuple(map(int, input().split()))
for i in range(list_len - 1):
    if integer_list[i] in integer_list[i+1:]:
        print('NO')
        break
else:
    print('YES')

### FIXED CODE ###

list_len = int(input())
integer_list = input().split()
if list_len == len(set(integer_list)):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

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

l = []
l.append(a[0])
cou =[]
for i in range(1,n):
    b = a[i]
    for j in range(len(l)):
      if b==l[j]:
        cou.append(b)
        break
      if b%l[j]==0:
          break
    else:
        l.append(b)
print(len(l)-len(set(cou)))

### FIXED CODE ###

counter = [0 for i in range(10**6+1)]
n = int(input())
a = sorted(list(map(int,input().split())))
for i in a:
  counter[i] += 1
l  = [0 for i in range(10**6+1)]
cou = 0
for i in range(n):
  b = a[i]
  if l[b]==0:
    cou += 1
    for j in range(b,10**6+1,b):
      l[j] = 1
    if counter[b]>=2:
      cou -=1
print(cou)
### BUGGY CODE ###

n, k = [int(e) for e in input().split(' ')]
h_list = [int(e) for e in input().split(' ')]

dp_list = [0]

for i in range(1, n):
    dist_min = float("inf")
    for j in range(max(0, i - k), i):
        dist = abs(h_list[i] - h_list[j]) + dp_list[j]
        dist_min = min(dist_min, dist)
    dp_list.append(dist_min)

print(dp_list[-1])  # 出力


### FIXED CODE ###

n, k = [int(e) for e in input().split(' ')]
h_list = [int(e) for e in input().split(' ')]

dp_list = [0]

for i in range(1, n):
    dist_min = float("inf")
    for j in range(max(0, i - k), i):
        dist = abs(h_list[i] - h_list[j]) + dp_list[j]
        dist_min = min(dist_min, dist)
    dp_list.append(dist_min)

print(dp_list[-1])  # 出力
### BUGGY CODE ###

mod = 998244353

A, B, C, D = map(int, input().split())

dp = [0] * B + [pow(A, i, mod) for i in range(D + 1 - B)]
for a in range(A + 1, C + 1):
    T = [0] * (D + 1)
    for b in range(B, D + 1):
        T[b] = (a * T[b - 1] + b * dp[b] - (a - 1) * (b - 1) * dp[b - 1]) % mod
    dp = T

print(dp[D])

### FIXED CODE ###

mod = 998244353

A, B, C, D = map(int, input().split())

dp = [0] * (D + 1)
dp[B:D + 1] = [pow(A, i, mod) for i in range(D + 1 - B)]

for a in range(A + 1, C + 1):
    T = [0] * (D + 1)
    for b in range(B, D + 1):
        T[b] = (a * T[b - 1] + b * dp[b] - (a - 1) * (b - 1) * dp[b - 1]) % mod
    dp = T

print(dp[D])
### BUGGY CODE ###

if __name__ == '__main__':
    N, M, K = map(int, input().split()) 
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    acc_A = []
    acc_B = []
    acc_A.append(0)
    acc_B.append(0)
    
    sum_a = 0
    sum_b = 0

    for a in A:
        sum_a += a
        acc_A.append(sum_a)

    for b in B:
        sum_b += b
        acc_B.append(sum_b)

    large_ar = []
    small_ar = []

    if N > M:
        large_ar = acc_A
        small_ar = acc_B
    else:
        large_ar = acc_B
        small_ar = acc_A
    
    ans = 0
    for i in range(len(small_ar)):
        for j in range(len(large_ar)):
            if large_ar[j] + small_ar[i] <= K:
                ans = max(ans, i+j)
            else: break
    print(ans)

### FIXED CODE ###

if __name__ == '__main__':
    N, M, K = map(int, input().split()) 
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    acc_A = []
    acc_B = []
    acc_A.append(0)
    acc_B.append(0)
    
    sum_a = 0
    sum_b = 0

    for a in A:
        sum_a += a
        acc_A.append(sum_a)

    for b in B:
        sum_b += b
        acc_B.append(sum_b)

    large_ar = []
    small_ar = []

    if N > M:
        large_ar = acc_A
        small_ar = acc_B
    else:
        large_ar = acc_B
        small_ar = acc_A
    
    ans = 0
    for i in range(len(small_ar)):
        for j in range(ans-i+1, len(large_ar)):
            if large_ar[j] + small_ar[i] <= K:
                ans = max(ans, i+j)
            else: break
    print(ans)
### BUGGY CODE ###

def main():
    s=input()
    n = len(s)
    dp = [[0]*(13) for _ in range(100005)]
    MOD = 10**9 + 7
    dp[0][0]=1

    for i in range(n):
        c=0
        if(s[i]=="?"):c=-1
        else:c = int(s[i])

        for j in range(10):
            if(c!=-1 and c!=j):
                continue
            for ki in range(13):
                dp[i+1][(ki*10+j)%13] += dp[i][ki]

        for j in range(13):
            dp[i+1][j]%=MOD
    res = dp[n][5]

    print(res)





if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s=input()
    n = len(s)
    dp = [[0]*(13) for _ in range(100005)]
    MOD = 10**9 + 7
    dp[0][0]=1

    for i in range(n):
        c=0
        if(s[i]=="?"):c=-1
        else:c = int(s[i])

        for j in range(10):
            if(c!=-1 and c!=j):
                continue
            for ki in range(13):
                dp[i+1][(ki*10+j)%13] += dp[i][ki]

        for j in range(13):
            dp[i+1][j]%=MOD
    res = dp[n][5]

    print(res)





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

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

c=sorted(list(map(int,input().split())))

i=m
while i>0:
    c[-1]=c[-1]//2
    c=sorted(c)
    i-=1

print(sum(c))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())

c=list(map(lambda x: int(x)*-1,input().split()))
#heapqでは最小値しか取り出せないので最大値をとるばあには－１をかけておく

heapq.heapify(c)  #リストを優先度付きキューに
for i in range(m):
    cmin=heapq.heappop(c)  #最小値の取り出し
    heapq.heappush(c,(-1)*(-cmin//2))#最小値を2で割った商をリストに追加

print(-sum(c))
### BUGGY CODE ###

N, *a = map(int, open(0).read().split())
print(min(abs(sum(a[:i]) - sum(a[i:])) for i in range(1, N)))

### FIXED CODE ###

from itertools import accumulate
N, *a = map(int, open(0).read().split())
x = list(accumulate(a[:-1]))
y = list(accumulate(a[:0:-1]))[::-1]
print(min(abs(i - j) for i, j in zip(x, y)))
### BUGGY CODE ###

S = ''


def we_love_abc()->int:
    global S
    ABC = 'ABC'

    dp = [0, 0, 0, 0]
    dp[3] = 1

    for c in reversed(S):
        if c == '?':
            m, m1 = 3, 3
        else:
            m, m1 = 1, 1

        for j in range(3):
            m2 = 1 if c == '?' or c == ABC[j] else 0
            dp[j] = m1 * dp[j] + m2 * dp[j+1]
        dp[3] = m * dp[3]

    return dp[0] % 1000000007


if __name__ == "__main__":
    S = input()
    ans = we_love_abc()  # S)
    print(ans)


### FIXED CODE ###

def we_love_abc(S: str)->int:
    ABC = 'ABC'
    MOD = 1000000007

    dp = [0, 0, 0, 0]
    dp[3] = 1

    for c in reversed(S):
        for j in range(3):
            m1 = 3 if c == '?' else 1
            m2 = 1 if c == '?' or c == ABC[j] else 0
            dp[j] = (m1 * dp[j] + m2 * dp[j+1]) % MOD
        dp[3] = (3 if c == '?' else 1) * dp[3]
        dp[3] %= MOD

    return dp[0] % MOD


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)