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

def GCD(a, b):
    """ Euclidean algorithm"""
    if a < b: (a, b) = (b, a)
    if b == 0: return a
    m = a % b
    while m != 0:
        a = b
        b = m
        m = a % b
    return b

N = int(input())
A = [ int(v) for v in input().split() ]

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < 1 and v < 1e9: raise()

result = []
for skip in range(0, N):
    l = 0
    r = 0
    for i in range(0, skip):
        l = GCD(l, A[i])
    for i in range(skip+1, N):
        r = GCD(r, A[i])
    n = GCD(l, r)
#   print(l,r,n)
    result.append(n)
print(max(result))

### FIXED CODE ###

def GCD(a, b):
    """ Euclidean algorithm"""
    if a < b: (a, b) = (b, a)
    if b == 0: return a
    m = a % b
    while m != 0:
        a = b
        b = m
        m = a % b
    return b

N = int(input())
A = [ int(v) for v in input().split() ]

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < 1 and v < 1e9: raise()


l_list = []
l = 0
for i in range(0, N):
    l = GCD(l, A[i])
    l_list.append( l )

r_list = []
r = 0
for i in range(-1, -(N+1), -1):
    r = GCD(r, A[i])
    r_list.append( r )

n = []    
for i in range(0, N):
    if i-1 < 0:
        l = 0
    else:
        l = l_list[i-1]
    if N-i-2 < 0:
        r = 0
    else:
        r = r_list[N-i-2]
    n.append(GCD(l, r))
print(max(n))
### BUGGY CODE ###

N,M,K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

for i in range(1, N+1):
    A[i] += A[i-1]
for i in range(1, M+1):
    B[i] += B[i-1]

ans = 0

for i in range(N+1):
    if A[i] > K: break
    else:
        for j in range(M+1):
            if A[i] + B[j] > K: break
            elif ans < i + j:
                ans = i + j

print(ans)

### FIXED CODE ###

N,M,K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

for i in range(1, N+1):
    A[i] += A[i-1]
for i in range(1, M+1):
    B[i] += B[i-1]

ans = 0
j = M

for i in range(N+1):
    if A[i] > K:
        break
    while A[i] + B[j] > K:
        j -= 1
    ans = max(ans, i + j)

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

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

while 1:
    if m%n==0:
        print(m//n)
        exit()
    n+=1



### FIXED CODE ###

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

def make_divisors(n,m):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i>=m:
                divisors.append(i)
            if i != n // i:
                if n//i>=m:
                    divisors.append(n//i)

    divisors.sort()
    return divisors

test=make_divisors(m,n)
print(m//min(test))
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
s=1
for i in range(1,N):
  if P[i]<=min(P[0:i]):
    s+=1
print(s)

### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
s=1
m=P[0]
for i in range(1,N):
  if P[i]<=m:
    m=P[i]
    s+=1
print(s)
### BUGGY CODE ###

k = int(input())
n = 7
c = 1
if k % 2 == 0:
  print(-1)
else:
  while True:
    tmp = n % k
    if tmp == 0:
      print(c)
      break
    else:
      n = tmp * 10 + 7
      c += 1

### FIXED CODE ###

k = int(input())
n = 7
c = 1
f = 1
if k % 2 == 0:
  print(-1)
else:
  while c < 1000000:
    tmp = n % k
    if tmp == 0:
      print(c)
      f = 0
      break
    else:
      n = tmp * 10 + 7
      c += 1
  if f == 1:
    print(-1)
### BUGGY CODE ###

from collections import Counter


def slv(K, D):
    rl = Counter()
    r = Counter()
    rl[0] = 1

    M = 10**9 + 7
    for c in K:
        d = int(c)
        rln = Counter()
        rn = Counter()
        for rem, count in rl.items():
            rln[(rem + d) % D] += count
            rln[(rem + d) % D] %= M

        for rem, count in rl.items():
            for i in range(d):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        for rem, count in r.items():
            for i in range(10):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        rl = rln
        r = rn
    return (rl[0] + r[0] - 1) % M


K = input()
D = int(input())
print(slv(K, D))


### FIXED CODE ###

from collections import Counter


def slv(K, D):
    rl = Counter()
    r = Counter()
    rl[0] = 1

    M = 10**9 + 7
    for c in K:
        d = int(c)
        rln = Counter()
        rn = Counter()
        for rem, count in rl.items():
            rln[(rem + d) % D] += count
            rln[(rem + d) % D] %= M

        for rem, count in rl.items():
            for i in range(d):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        for rem, count in r.items():
            for i in range(10):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        rl = rln
        r = rn
    return (rl[0] + r[0] - 1) % M


K = input()
D = int(input())
print(slv(K, D))
### BUGGY CODE ###

n, m = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(m)]

PY_sort = sorted(PY, key=lambda x: x[1])
PY_sort.sort(key=lambda x: x[0])

ID = {}
for i in range(1, n + 1):
    T = [py for py in PY_sort if py[0] == i]
    for i, v in enumerate(T):
        id = "%06d%06d"%(v[0], i + 1)
        ID[v[1]] = id

for p, y in PY:
    print(ID[y])


### FIXED CODE ###

n, m = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(m)]

PY_sort = sorted(PY, key=lambda x: x[1])
PY_sort.sort(key=lambda x: x[0])

ID = {}
i, p = 1, PY_sort[0][0]
for v in PY_sort:
    if v[0] != p:
        i, p = 1, v[0]
    id = "%06d%06d"%(p, i)
    ID[v[1]] = id
    i += 1

for p, y in PY:
    print(ID[y])
### BUGGY CODE ###

n = int(input())
l = [int(input()) for i in range(n)]

#print(l)

check = [0]*n
go = 0
ans = 0

for i in range(n):
	#print(i)
	check[i] = go
	ans = ans + 1
	go = l[go]-1
	#print(go)
	#print(check)
	
	if go == 1:
		break
	
	if go in check:
		ans = -1
		break

print(ans)


### FIXED CODE ###

n = int(input())
l = [int(input()) for i in range(n)]

#print(l)

go = 0
ans = -1

for i in range(n):
	#print('----')
	#print(i)
	go = l[go]-1
	#print(go)

	if go == 1:
		if ans < 0:
			ans = i +1

#print('-----')
print(ans)
### BUGGY CODE ###

import re
N = int(input())
S = input()
cnt = 0
for i in range(10):
    for j in range(10):
        for h in range(10):
            patrn = r".*" + re.escape(str(i)) + r".*" + re.escape(str(j)) + r".*" + re.escape(str(h)) + r".*"
            result = re.match(patrn, S)
            if result != None:
                cnt += 1
print(cnt)

### FIXED CODE ###

import re
#import time
N = int(input())
S = input()
#start = time.time()
cnt = 0
for i in range(10):
    fir = S.find(str(i))
    if fir == -1:
        continue
    for j in range(10):
        sec = S.find(str(j), fir + 1)
        if sec == -1:
            continue
        for h in range(10):
            thi = S.find(str(h), sec + 1)
            if thi == -1:
                continue
            cnt += 1
print(cnt)
#stop = time.time()
#print(stop - start)
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    min = N
    mc = 0
    for i in range(0, N):
        m = S[i]
        l = S[:i]
        r = S[i:]
        c = 0
        c = mc
        for h in r:
            if h != 'W': c += 1
        if min > c: min = c
        if m != 'E': mc += 1
    print(min)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ec = S.count('E')
    tec = ec
    for k in S:
        if k == 'E':
            tec -= 1
        else:
            tec += 1
        ec = min(ec, tec)
    print(ec)

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


import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

n,a,b=getints()
hs=[getint() for _ in range(n)]
mx=max(hs)

min_cast = 0
max_cast = mx+1
c = a-b

while min_cast < max_cast:
    cast = (min_cast + max_cast) // 2
    values= list(filter(lambda s: s > 0, map(lambda s: s - b*cast, hs)))
    need = sum(map(lambda v: (v + c - 1) // c, values))
    if need <= cast:
        max_cast = cast
    else:
        min_cast = cast + 1

print(min_cast)

### FIXED CODE ###


import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

n,a,b=getints()
hs=[getint() for _ in range(n)]
mx=max(hs)

min_cast = 0
max_cast = mx+1
c = a-b

hs = list(sorted(hs,reverse=True))

while min_cast < max_cast:
    cast = (min_cast + max_cast) // 2
    #values= list(filter(lambda s: s > 0, map(lambda s: s - b*cast, hs)))
    #need = sum(map(lambda v: (v + c - 1) // c, values))
    need = 0
    dec = b * cast
    for v in hs:
        v = v - dec
        if v <= 0:
            break
        need += (v + c - 1) // c
    if need <= cast:
        max_cast = cast
    else:
        min_cast = cast + 1

print(min_cast)
### BUGGY CODE ###

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

ans = 1
for i in range(N):
  ans *= A[i]
    
if ans <= 10**18:
  print(ans)
else:
  print(-1)

### FIXED CODE ###

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

def main(A):
  if 0 in A:
    print(0)
    return
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  print(prod)
    
main(A)
### BUGGY CODE ###

s = input()
n = len(s)
count = 0

while True:
    if '10' in s:
        count += s.count('10') * 2
        s = s.replace('10','')
    elif '01' in s:
        count += s.count('01') * 2
        s = s.replace('01','')
    else:
        break

print(count)


### FIXED CODE ###

s = input()
print(min(s.count('0'),s.count('1'))*2)
### BUGGY CODE ###

K,S = [int(i) for i in input().split()]
patterns = 0

for x in range(K+1) :
    x = int(x)
    for y in range(K+1) :
        y = int(y)
        z = S - x - y
        if (0 <= z and z <= K) :
            patterns += 1

print(patterns)


### FIXED CODE ###

K,S = [int(i) for i in input().split()]
patterns = 0

for x in range(K+1) :
    for y in range(K+1) :
        z = S - x - y
        if (0 <= z and z <= K) :
            patterns += 1

print(patterns)
### BUGGY CODE ###

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]

# def gcd(x, y):
#     #print(x, y)
#     while x != 0 and y != 0:
#         x, y = max(x, y), min(x, y)
#         x %= y
#     return y

# def lcm(x, y):
#     return x * y // gcd(x, y)

# for i in range(1, n):
#     lcms = [0] * 2
#     for j in range(2):
#         lcms[j] = lcm(A[i][j], A[i-1][j])
#     print("lcms", lcms)
#     st = 0
#     op = 1
#     if lcms[0] > lcms[1]:
#         st = 1
#         op = 0
#     new_1 = (lcms[st] // A[i][st]) * A[i][op]
#     print(new_1)
#     if new_1 >= A[i-1][op]:
#         A[i][op] = new_1
#         A[i][st] = lcms[0]
#     else:
#         new_0 = lcms[op] // A[i][op] * A[i][st]
#         A[i][st] = new_0
#         A[i][op] = lcms[op]
#     print(A[i])

# print(sum(A[-1]))

for i in range(1, n):
    s = A[i][0]
    t = A[i][1]
    while not (A[i][0] >= A[i-1][0] and A[i][1] >= A[i-1][1]):
        A[i][0] += s
        A[i][1] += t
        # print(A[i-1], A[i])

print(sum(A[-1]))

### FIXED CODE ###

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]

# def gcd(x, y):
#     #print(x, y)
#     while x != 0 and y != 0:
#         x, y = max(x, y), min(x, y)
#         x %= y
#     return y

# def lcm(x, y):
#     return x * y // gcd(x, y)

# for i in range(1, n):
#     lcms = [0] * 2
#     for j in range(2):
#         lcms[j] = lcm(A[i][j], A[i-1][j])
#     print("lcms", lcms)
#     st = 0
#     op = 1
#     if lcms[0] > lcms[1]:
#         st = 1
#         op = 0
#     new_1 = (lcms[st] // A[i][st]) * A[i][op]
#     print(new_1)
#     if new_1 >= A[i-1][op]:
#         A[i][op] = new_1
#         A[i][st] = lcms[0]
#     else:
#         new_0 = lcms[op] // A[i][op] * A[i][st]
#         A[i][st] = new_0
#         A[i][op] = lcms[op]
#     print(A[i])

# print(sum(A[-1]))

for i in range(1, n):
    s = -(-A[i-1][0] // A[i][0])
    t = -(-A[i-1][1] // A[i][1])
    # print(i,s,t)
    for j in range(2):
        A[i][j] *= max(s, t)
    # print(A)
    
print(sum(A[-1]))
### BUGGY CODE ###

# coding: utf-8
# Here your code !
n = int(input())
pool = []
for i in range(n):
    a = input()
    if a not in pool:
        pool.append(a)
    else:
        pool.remove(a)
print(len(pool))

### FIXED CODE ###

# coding: utf-8
# Here your code !
n = int(input())
pool = {}
for i in range(n):
    a = int(input())
    if a not in pool:
        pool[a] = True
    else:
       del pool[a]
print(len(pool))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
dif=9999999999999999999
x=-1
ans=0
for i in range(N):
  long=abs(sum(A[i+1:])-sum(A[:i+1]))
  if long<dif:
    dif=long
    x=i+1
pl=max(sum(A[:x]),sum(A[x:]))
mi=min(sum(A[:x]),sum(A[x:]))
while mi<pl:
  mi+=1
  ans+=1
  if mi==pl:
    break
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
p=q=sum(A)
for i in range(N):
  p-=2*A[i]
  q=min(abs(p),q)
print(q)
### BUGGY CODE ###

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

ans = 1
for a in A: ans *= a

if ans > 10**18: print(-1)
else: print(ans)

### FIXED CODE ###

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

res = 1
for a in A:
    res = min(res*a, 10**18 + 1)
if res == 10**18 + 1: print(-1)
else: print(res)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

bit = [0] * 61
for i in range(N):
    for x in range(61):
        if 2**x > A[i]:
            break
        elif (1<<x) & A[i] > 0:
            bit[x] += 1

ans = 0
for i in range(61):
    ans += 2**i * (bit[i] * (N-bit[i]))
    ans %= MOD

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

bit = [0] * 61
for i in range(N):
    for x in range(61):
        if 2**x > A[i]:
            break
        elif (1<<x) & A[i] > 0:
            bit[x] += 1

ans = 0
for i in range(61):
    ans += 2**i * (bit[i] * (N-bit[i]))
    ans %= MOD

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

X = int(input())
len = 0
flag = False
for i in range(1,X+1):
    if flag:
        break
    for j in range(i):
        len += 1
        if len >= X:
            flag = True
            ans = i
            break
print(ans)

### FIXED CODE ###

import math
X = int(input())
print(math.ceil((-1+(8*X+1)**(1/2))/2))
### BUGGY CODE ###

# coding: utf-8
S = input()
Q = int(input())
for i in range(Q):
    q = input().split()
    if q[0] == "1":
        S = S[::-1]
    else:
        if q[1] == "1":
            S = q[2] + S
        else:
            S += q[2]
print(S)

### FIXED CODE ###

# coding: utf-8
from collections import deque
S = deque(input())
Q = int(input())
cnt = 0
for i in range(Q):
    q = input().split()
    if q[0] == "1":
        cnt += 1
    else:
        if (int(q[1]) + cnt) % 2 == 1:
            S.appendleft(q[2])
        else:
            S.append(q[2])
ans = "".join(S)
print(ans if cnt % 2 == 0 else ans[::-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

WV = []

N, W = [int(v) for v in input().strip().split(' ')]

for _ in range(N):
    WV.append([int(v) for v in input().strip().split(' ')])

cache = {}
def find(w, l):   # あとw持てるときの最大価値（lはすでにナップサックに入っているもの）
    if (w, l) in cache:
        return cache[(w, l)]
    mx = 0
    for i in range(N):
        if w - WV[i][0] < 0 or l & (1 << i):
            continue
        mx = max(mx, WV[i][1] + find(w - WV[i][0], l + 1 << i))
    cache[(w, l)] = mx
    return mx

print(find(W, 0))


### FIXED CODE ###

import numpy as np
import sys

N, W = [int(v) for v in input().strip().split(' ')]
dp = np.zeros(W + 1, dtype = 'uint64')

for _ in range(N):
    w, v = [int(v) for v in sys.stdin.readline().split(' ')]
    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])

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

mod=10**9+7
n=int(input())
a=1
for i in range(1,n+1):
  a*=i
print(a%mod)

### FIXED CODE ###

mod=10**9+7
n=int(input())
a=1
for i in range(1,n+1):
  a*=i
  a%=mod
print(a)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    n, d, a = map(int, input().split())
    XH = []
    for i in range(n):
        x, h = map(int, input().split())
        XH.append((x, h))

    XH.sort()
    from collections import deque
    q = deque()

    ans = 0
    import copy
    for x, h in XH:
        nq = deque()
        while q:
            r, s = q.popleft()
            if r+d < x:
                continue
            else:
                h -= s
                nq.append((r, s))
        #print(x, h)
        if h > 0:
            if h%a == 0:
                b = h//a
                ans += b
                nq.append((x+d, a*b))
            else:
                b = h//a+1
                ans += b
                nq.append((x+d, a*b))
        q = copy.copy(nq)
        #print(q)
        #print(ans)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

n, d, a = map(int, input().split())
l = [[0, 0] for _ in range(n)]
for i in range(n):
  x, h = map(int, input().split())
  l[i][0] = x
  l[i][1] = h
  
l.sort()
from collections import deque
d = 2*d
q = deque([])
total = 0

ans = 0
for i in range(n):
  x = l[i][0]
  h = l[i][1]
  if q:
    while q[0][0] < x:
      total -= q[0][1]
      q.popleft()
      if not q:
        break
  h -= total
  if h > 0:
    num = (h+a-1)//a
    ans += num
    damage = num*a
    total += damage
    q.append([x+d, damage])

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

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
    b.append(a[i])
    b = b[::-1]
print(*b)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
odd = a[0::2]
even = a[1::2]
if n % 2 == 1:
    odd = odd[::-1]
    ans = odd + even
else:
    even = even[::-1]
    ans = even + odd
print(*ans)
### BUGGY CODE ###

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

b=[0 for i in range(N)]

for k in range(K):
    
    for i in range(N):
        l1=a[i]+1
        for j in range(l1):
            if(i+j<N):
                b[i+j]+=1
            if(i-j>=0 and (i-j)!=(i+j)):
                b[i-j]+=1
    
    for i in range(N):
        a[i]=b[i]
        b[i]=0

            
            
for i in range(N):
    print(a[i],"",end="")

### FIXED CODE ###

import numpy as np
from numba import jit
@jit(cache = True)
def solve(n,k,A):
    l,r=0,0
    for i in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for x,y in enumerate(list(A)):
            l=max(0,x-y)
            r=min(n,x+y+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
X=solve(n,k,A)
print(*X,sep=' ')
### BUGGY CODE ###

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

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

ret = []
tb = 0
i = 0
for i in range(n):
    ret.extend([a[i]] * b[i])

ret = sorted(ret)
print(ret[k-1])

### FIXED CODE ###

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

items = dict()
for _ in range(n):
    ta, tb = map(int, input().split())
    if ta in items.keys():
        items[ta] += tb
    else:
        items[ta] = tb

items = sorted(items.items())

tb = 0
key = 0
for key, val in items:
    tb += val
    if tb >= k:
        break
print(key)
### BUGGY CODE ###

n, k, q = map(int, input().split())
s = [k for i in range(n)]
for i in range(q):
    z = int(input())
    for j in range(n):
        if j != z - 1:
            s[j] -= 1
        
for i in range(n):
    if s[i] <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n, k, q = map(int, input().split())
s = [k for i in range(n)]
d = {}
for i in range(q):
    z = int(input())
    if z-1 not in d:
        d[z-1] = 1
    else:
        d[z-1] += 1 

for i in range(n):
    if i in d:
        s[i] = s[i] - q + d[i]
        if s[i] > 0:
            print('Yes')
        else:
            print('No')
    else:
        s[i] -= q
        if s[i] > 0:
            print('Yes')
        else:
            print('No')
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
S = input()
from collections import defaultdict
from bisect import bisect_left
a = []
b = []
c = []
# a = defaultdict(list)
# b = defaultdict(list)
# c = defaultdict(list)
q = []

for e,s in enumerate(S):
    if s == "A" :
        a.append(e)
    if s == "B" :
        b.append(e)
    if s == "C" :
        c.append(e)
    if s == "?":
        a.append(e)
        b.append(e)
        c.append(e)
        q.append(e)

ans = 0
MOD = int(1e9+7)
for ea in a:
    # print("ea: ", ea, a)
    for ib in range( bisect_left(b, ea+1), len(b)):
        eb = b[ib]
        # print("\teb: ", eb, b)
        # print("\t\tec: ", bisect_left(c, eb+1), "c: ", c, "ans += ", len(c) - bisect_left(c,eb+1) )
        for ic in range(bisect_left(c, eb+1), len(c)):
            ec = c[ic]
            qcnt = len(q) - (1 if ea in q else 0) - (1 if eb in q else 0) - (1 if ec in q else 0)
            ans += pow(3, qcnt, MOD) 

        ans %= MOD
        # ans += len(c) - bisect_left(c, eb+1)  
        # ans += (len(c) - bisect_left(c, eb+1)  ) ** pow(3, 
print(ans % MOD)
    


### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
S = input()
from collections import defaultdict
from bisect import bisect_left, bisect_right
a = []
b = []
c = []
# a = defaultdict(list)
# b = defaultdict(list)
# c = defaultdict(list)
q = []

for e,s in enumerate(S):
    if s == "A" :
        a.append(e)
    if s == "B" :
        b.append(e)
    if s == "C" :
        c.append(e)
    if s == "?":
        q.append(e)

ans = 0
MOD = int(1e9+7)

for eb in b:
    range_a = bisect_right(a, eb-1)
    # print("eb: {eb}, bisect_right({a}, {eb1}): {bis}".format
            # (eb = eb, a=a, eb1=eb-1, bis=bisect_right(a,eb-1)))
    range_c = len(c) - bisect_left(c, eb+1)
    
    range_cq = len(q) - bisect_left(q, eb+1)
    range_aq = bisect_right(q, eb-1)

    ans += range_a*range_c * pow(3, len(q), MOD) % MOD
    ans %= MOD
    if len(q)>=1:
        ans += range_a*range_cq * pow(3, len(q)-1, MOD)
        ans += range_aq*range_c * pow(3, len(q)-1, MOD)
        ans %= MOD
    if len(q)>=2:
        ans += range_aq*range_cq * pow(3, len(q)-2, MOD)
        ans %= MOD
for eq in q:
    # print("eb: {eb}, bisect_right({a}, {eb1}): {bis}".format
            # (eb = eq, a=a, eb1=eq-1, bis=bisect_right(a,eq-1)))
    range_a = bisect_right(a, eq-1)
    range_c = len(c) - bisect_left(c, eq+1)
    range_cq = len(q) - bisect_left(q, eq+1)
    range_aq = bisect_right(q, eq-1)

    ans += range_a*range_c * pow(3, len(q)-1, MOD)
    ans %= MOD
    if len(q) >= 2:
        ans += range_a*range_cq * pow(3, len(q)-2, MOD)
        ans += range_aq*range_c * pow(3, len(q)-2, MOD)
        ans %= MOD
    if len(q) >= 3:
        ans += range_aq*range_cq * pow(3, len(q)-3, MOD)
        ans %= MOD
    
print(ans % MOD)
### BUGGY CODE ###

import numpy as np
mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))
A = np.array(A, dtype = np.int64)
tmp = 0
for i in range(61):
    tmp_0 = 0
    for j in range(N):
        if ((A[j] >> i) & 1) == 0:
            tmp_0 += 1
    tmp += ((tmp_0)*(N - tmp_0)*(2**i)) % mod
print(tmp % mod)

### FIXED CODE ###

import numpy as np
mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))
A = np.array(A, dtype = np.int64)
tmp = 0
for i in range(61):
    tmp_1 = np.count_nonzero(A & 1)
    tmp += ((tmp_1)*(N - tmp_1)*(2**i)) % mod
    A = A >> 1
print(tmp % mod)