Harryxun/stf_run huggingface dataset:
import sys
import copy
import string
import  math
from _bisect import *
from collections import *
from operator import itemgetter
from math import factorial
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

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

    divisors.sort()
    return divisors

li = make_divisors(ni())
ans = 10000000000000000
for i in range(len(li) // 2):
    f = max(len(str(li[i])), len(str(li[-(i+1)])))
    ans = min(f, ans)
if len(li) % 2 != 0:
    if len(li) == 1
        ans = 1
    else:
        ans = min(len(str(li[len(li)//2 + 1])), ans)
print(ans)


### FIXED CODE ###

import sys
import copy
import string
import  math
from _bisect import *
from collections import *
from operator import itemgetter
from math import factorial
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

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

    divisors.sort()
    return divisors

n = ni()
li = make_divisors(n)
ans = 10000000000000000
for i in range(len(li) // 2):
    if li[i] * li[-(i+1)] == n:
        f = max(len(str(li[i])), len(str(li[-(i+1)])))
        ans = min(f, ans)
if len(li) % 2 != 0:
    if len(li) == 1:
        ans = 1
    else:
        print()
        ans = min(len(str(li[len(li)//2])), ans)
print(ans)
a = input()

st = str(a)


if a[1:4] == "000":
  print(0)

else:
  z = a[1:4]
  print(1000 - int(z))


### FIXED CODE ###

a = input()

st = str(a)


if st[-3:] == "000":
  print(0)


else:
  z = st[-3:]
  print(1000 - int(z))
[N,L] = [int(x) for x in input().split()]
A = {}
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count >= N : break
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
A, B = map(int, input().split())
print(max(max(A+B, A-B), A*B))

### FIXED CODE ###

A, B = map(int, input().split())
print(max(max(A+B, A-B), A*B))
s=input()

def walk(s):
  ls=len(s)
  if ls%2==1:
    print("NO")
    return
  nc=0
  sc=0
  wc=0
  ec=0
  for i in range(ls):
    if s[i]="W":
      wc+=1
    elif s[i]="E":
      ec+=1
    elif s[i]="N":
      nc+=1
    else:
      sc+=1
  if wc==ec and nc==sc:
    print("YES")
    return
  else:
    print("NO")
    return
walk(s)
    

### FIXED CODE ###

s = input()


def walk(s):
    ls = len(s)
    nc = 0
    sc = 0
    wc = 0
    ec = 0
    l=[]
    for i in range(ls):
        if s[i] == "W":
            wc += 1
            l.append(wc)
        elif s[i] == "E":
            ec += 1
            l.append(ec)
        elif s[i] == "N":
            nc += 1
            l.append(nc)
        else:
            sc += 1
            l.append(sc)
    if (wc>0 and ec==0) or (wc==0 and ec>0) or (nc==0 and sc>0) or (nc>0 and sc==0):
        print("No")
        return
    
    else:
        print("Yes")
        return
walk(s)
n=int(input())
list=sorted([int(x) for x in input().split()])
print(a[0],a[-1],sum(list))

### FIXED CODE ###

n=int(input())
list=sorted([int(x) for x in input().split()])
print(list[0],list[-1],sum(list))
n = int(input())
a = int(input())
b = int(input())

if n == 1:
  print("Hello World")
if n == 2:
  print(a + b)

### FIXED CODE ###

n = int(input())

if n == 1:
  print("Hello World")
if n == 2:
  a = int(input())
  b = int(input())
  print(a + b)
l,r=map(int,input().split())
minimum=1000000000
for i in range(l, r+1):
    for j in range(i+1,r+1):
        minimum=min(minimum,((i*j)%2019))
        if minimum==0:
            break
    if miminum ==0:
        break
print(minimum)

### FIXED CODE ###

l,r=map(int,input().split())
if r>l+4040:
    r=l+4040
dif=r-l
minimum=1000000000
for i in range(l%2019,l%2019 + dif+1):
    for j in range(i+1,l%2019 +dif +1):
        minimum=min(minimum,((i*j)%2019))
print(minimum)
import math
a,b=[int(i) for i in input().split()]
#def lcm(x,y):
    #return (x*y) // math.gcd(x,y)

  
  
z= (a*b)/math.gcd(a,b)
print(int(z))

### FIXED CODE ###

A, B=[int(i) for i in input().split()]

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a, b):
	return a * b // gcd (a, b)
  
print(lcm(A,B))
from math import sin, cos, pi, sqrt
a, b, c = map(int, input().split())
s = a*b*sin(pi*c/180)/2
c = sqrt(a**2 + b**2 -a*b*2*cos(pi*c/180))
h = 2*S/a
print(s)
print(a+b+c)
print(h)


### FIXED CODE ###

from math import sin, cos, pi, sqrt
a, b, c = map(int, input().split())
s = a*b*sin(pi*c/180)/2
c = sqrt(a**2 + b**2 -a*b*2*cos(pi*c/180))
h = 2*s/a
print(s)
print(a+b+c)
print(h)
from decimal import Decimal
T = tuple(map(Decimal, input().split()))

A = list(map(Decimal, input().split()))
B = list(map(Decimal, input().split()))


ans = 0
if A[0] < B[0]:
    tmp = (A[0], A[1])
    A[0], A[1] = B[0], B[1]
    B[0], B[1] = tmp[0], tmp[1]

a = abs(T[0]*A[0] - T[0]*B[0])

b = T[0]*(B[0]-A[0])+T[1]*(B[1]-A[1])


if b == 0:
    print("Infinity")
elif b < 0:
    print(0)
    exit(0)
else:
    ans += 1
    if b > a:
        print(1)
    elif b == a:
        print("infinity")
    else:
        if a % b == 0:
            print((a*2)//b)
        else:
            print(((a//b)*2 + 1)


### FIXED CODE ###

from decimal import Decimal
T = tuple(map(Decimal, input().split()))

A = list(map(Decimal, input().split()))
B = list(map(Decimal, input().split()))


ans = 0
if A[0] < B[0]:
    tmp = (A[0], A[1])
    A[0], A[1] = B[0], B[1]
    B[0], B[1] = tmp[0], tmp[1]

a = abs(T[0]*A[0] - T[0]*B[0])

b = T[0]*(B[0]-A[0])+T[1]*(B[1]-A[1])


if b == 0:
    print("infinity")
elif b < 0:
    print(0)
    exit(0)
else:
    ans += 1
    if b > a:
        print(1)
    elif b == a:
        print("infinity")
    else:
        if a % b == 0:
            print((a//b)*2)
        else:
            print((a//b)*2 + 1)
a = int(input())
unchi = 0
while a>=1:
    a -= 1
    if 99999 >= a >= 10000:
        unchi += 1
    elif 999 >= a >= 100:
        unchi += 1
    elif 9 >= a >= 1:
        unchi += 1
print(unchi)


### FIXED CODE ###

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

X = b + c - a
if X >= 0:
    print(X)
else:
    print(0)
n, m = map(int, input().split())
# S = [None] * m
# C = [None] * m
dic = {}
for i in range(m):
    s, c = map(int, input().split())
    try:
        _ = dic[s]
    except KeyError:
        dic[s] = c
    else:
        if (dic[s] != c):
            print(-1)
            exit()

ans = '0' * n
for k, v in dic.items():
    ans = ans[:k - 1] + str(v) + ans[k:]

try:
    digit1 = dic[1]
except KeyError:
    digit1 = 1

if (digit1 == 0 and ans[0] == '0'):
    print(-1)
    exit()
elif (dic[1] == 0):
    ans = '1' + ans[1:]

print(ans)


### FIXED CODE ###

# n, m = map(int, input().split())
# if (m == 0):
#     print('1' + '0' * (n - 1))
#     exit()
# dic = {}
# for i in range(m):
#     s, c = map(int, input().split())
#     try:
#         _ = dic[s]
#     except KeyError:
#         if (s == 1 and c == 0):
#             print(-1)
#             exit()
#         dic[s] = c
#     else:
#         if (dic[s] != c):
#             print(-1)
#             exit()

# ans = '0' * n
# for k, v in dic.items():
#     ans = ans[:k - 1] + str(v) + ans[k:]

# try:
#     digit1 = dic[1]
# except KeyError:
#     digit1 = 1

# if (digit1 == 0):
#     ans = '1' + ans[1:]

# print(ans)
n, m = map(int, input().split())
if (n == 1 and m == 0):
    print(0)
    exit()
if (m == 0):
    print('1' + '0' * (n - 1))
    exit()
dic = {}
for i in range(m):
    s, c = map(int, input().split())
    try:
        _ = dic[s]
    except KeyError:
        if (s == 1 and c == 0 and n >= 2):
            print(-1)
            exit()
        dic[s] = c
    else:
        if (dic[s] != c):
            print(-1)
            exit()

ok = False
if (n == 1):
    for k, v in dic.items():
        print(v)
        exit()
else:
    for i in range(10 ** (n - 1), 10 ** n):
        for k, v in dic.items():
            if (str(i)[k - 1] == str(v)):
                ok = True
            else:
                ok = False
                break
        else:
            if (ok):
                print(i)
                exit()
def check(N, K):
    if N - 1 == K:
        for i in range(i + 2, N + 1):
            print(1, i)
        return
    elif N - 2 == K:
        for i in range(1, N):
            print(i, i+1)
        return
    elif N >= K:
        return
    else:
        print(-1)
        return



if __name__ == "__main__":
    N, K = map(int, input().split())
    check(N, K)


### FIXED CODE ###

def check(N, K):
    if K <= (N - 1)*(N-2) /2:
        k = int((N - 1)*(N-2)/2 - K)
        print(N-1 + k)
        for i in range(2, N+1):
            print(1, i)
        l = 2
        r = 3
        if k != 0:
            for i in range(k):
                if l > N or r > N:
                    break
                print(l, r)
                r+=1
                if r == N+1:
                    l+=1
                    r=l+1
        return
    else:
        print(-1)
        return


if __name__ == "__main__":
    N, K = map(int, input().split())
    check(N, K)
import sys
a=int(sys.argv[1])
b=int(sys.argv[2])
sum=a*500
if b>sum:
	print("Yes")
else:
 	print("NO")

### FIXED CODE ###

a,b=map(int,input().split( ))
sum=a*500
if sum>=b:
  print("Yes")
else:
  print("No")
exit()
a,b=input().split()
r=''
x=0
for i in b:
  if i=='.':
    r=r
  elif i!='0':
    x=1
    r=r+i
  elif x==1 and i=='0':
    r=r+i
A=int(a)
B=int(r)
print(A*B//100)
    

### FIXED CODE ###

a,b=input().split()
r=''
x=0
for i in b:
  if i=='.':
    r=r
  elif i!='0':
    x=1
    r=r+i
  elif x==1 and i=='0':
    r=r+i
if len(r)==0:
  r='0'
A=int(a)
B=int(r)
print(A*B//100)
n=int(input())
h=list(map(int,input().split()))
cos={0:0,1:abs(h[1]-h[0])}
def cost(x):
  if x not in cos:
    d1=cost(x-1)+abs(h[x]-h[x-1])
    d2=cost(x-2)+abs(h[x]-h[x-2])
    cos[x]=min(d1,d2)
    return cos[x]
  else:
    return cos[x]
  
print(cost(n-1))

### FIXED CODE ###

n=int(input())
import sys
sys.setrecursionlimit(10 ** 6)
h=list(map(int,input().split()))
cos={0:0,1:abs(h[1]-h[0])}
def cost(x):
  if x not in cos:
    d1=cost(x-1)+abs(h[x]-h[x-1])
    d2=cost(x-2)+abs(h[x]-h[x-2])
    cos[x]=min(d1,d2)
    return cos[x]
  else:
    return cos[x]
  
print(cost(n-1))
import math

#試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return 'prime number'
    else:
        factor.append(n)
        return factor
      
n = int(input())
n_list = trial_division(n)
ans = 0
z = []
for i in range(len(n_list)):
  if n_list[i] == 1:
    break
  else:
    if n % n_list[i] == 0:
      z.append(n_list[i])
      n = n / n_list[i]
      ans += 1
print(ans)

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
      
n = int(input())
n_list = factorization(n)
oh = []
for i in range(len(n_list)):
  num = n_list[i][0] #2の
  kata = n_list[i][1] #3乗
  for i in range(1, kata+1):
    oh.append(num ** i)
oh.sort()
ans = 0
z = []
for i in range(len(oh)):
  if oh[i] == 1:
    break
  else:
    if n % oh[i] == 0 and oh[i] not in z:
      z.append(oh[i])
      n = n / oh[i]
      ans += 1
print(ans)
N = int(input())
K = int(input())

def keta1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])

def keta2(n):
    s = str(n)
    cnt = [0] * 101
    for i in range(2, 101):
        cnt[i] = 9 * 9 * (i - 1)
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta1(10 ** (len(s) - 1) - 1) + keta1(int(s[1:]))
    return res

def keta3(n):
    s = str(n)
    cnt = [0] * 101
    for i in range(3, 101):
        cnt[i] = 9 * 9 * 9 * (i - 1) * (i - 2) // 2
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta2(10 ** (len(s) - 1) - 1) + keta2(int(s[1:]))
    return res

if K == 1:
    print(keta1(N))
elif K == 2:
    print(keta2(N))
elif K == 3:
    print(keta3(N))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N = int(input())
K = int(input())

LN = len(str(N))

def keta1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])
#print(keta1(N))


def keta2(n):
    if n < 10:
        return 0
    cnt2 = [0] * 101
    for i in range(2, 101):
        cnt2[i] = 9 * 9 * (i - 1)
    tmp2 = 0
    for i in range(len(str(n))):
        tmp2 += cnt2[i]
    tmp2 += (int(str(n)[0]) - 1) * keta1((10 ** (len(str(n))  - 1)) - 1) + keta1(int(str(n)[1:]))
    return tmp2

def keta3(n):
    cnt3 = [0] * 101
    for i in range(3, 101):
        cnt3[i] = 9 * 9 * 9 * (i - 1) * (i - 2) // 2
    tmp3 = 0
    for i in range(len(str(n))):
        tmp3 += cnt3[i]
    tmp3 += (int(str(N)[0]) - 1) * keta2((10 ** (len(str(n))  - 1)) - 1) + keta2(int(str(n)[1:]))
    
    return tmp3

if K == 1:
    print(keta1(N))
elif K == 2:
    print(keta2(N))
elif K == 3:
    print(keta3(N))
n = int(input())
count = 0
for i in range(n):
    x = int(input())
    if (x < 2):
        break
    if (x == 2):
        count += 1
    else:
        while (j * j <= x):
            if (x % j == 0):
                break
            else:
                count += 1
            j = j + 2
print(count)
 

### FIXED CODE ###

n = int(input())
count = 0
for i in range(n):
    x = int(input())
    if (x == 2):
        count += 1
    elif (x % 2 == 0):
        continue
    else:
        if (pow(2, x - 1, x) == 1):
            count += 1
print(count)
a, b = [input() for i in range(2)]

count = 0
out = 0
if a == b:
  print("0")
else:
  c = list(a)
  d = list(b)
  for i in c:
    if i == d[count]:
      pass
    else:
      out = out + 1
    count = count + 1
  print(str(out))

### FIXED CODE ###

a = int(input())

print(str(a + (a ** 2) + (a ** 3)))
def main():
    n, k, *x = map(int, open(0).read().split())
    ans = min([x[i + k - 1] - x[i] + min(abs(x[i + k - 1]), abs(x[i])) for i in range(n - k)])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, k, *x = map(int, open(0).read().split())
    f = lambda i: x[i + k - 1] - x[i] + min(abs(x[i + k - 1]), abs(x[i]))
    l = f(0)

    for i in range(n - k + 1):
        y = f(i)
        if y < l:
            l = y

    print(l)


if __name__ == '__main__':
    main()
def gcd(A, B):
    while B != 0:
        A, B = B, A%B
    return A

N, M = map(int, input().split())
S = input()
T = input()
can = True
agc = N // gcd(N, M) * M
L_N = agc // N
L_M = agc // M
i = 0

while i*L_M < agc and i*L_N < agc:
    if S[i*L_M] != T[i*L_N]:
        can = False
        break
    i += 1

if can:
    print(agc)
else:
    print(-1)

### FIXED CODE ###

def gcb(A, B):
    while B != 0:
        A, B = B, A%B
    return A

N, M = map(int, input().split())
S = input()
T = input()
can = True
agc = N // gcb(N, M) * M
L_N = agc // N
L_M = agc // M
i = 0
while i*L_M < N and i*L_N < M:
    if S[i*L_M] != T[i*L_N]:
        can = False
        break
    i += 1

if can:
    print(agc)
else:
    print(-1)
n=int(input())
a=list(map(int,input().split()))
s=set(a)

sei=[]
cho=[]



for i in s:
    x= a.count(i)
    
    if x >= 4:
        sei.append(i)
    elif x >= 2:
        cho.append(i)

cho2=sorted(cho,reverse=True)
        
if sei==[] and len(cho)<2:        
    print(0)
    exit()
else:
    print(max(max(sei)**2,cho2[0]*cho2[1],max(sei)*cho2[0]))



### FIXED CODE ###

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


count=0
ans=[]
flag=0
for i in range(1,n):
    if a[i]==a[i-1] and flag==1:
        flag=0


    elif a[i]==a[i-1] and flag==0:
        count += 1
        ans.append(a[i])
        flag=1

    elif a[i] != a[i-1]:
        flag=0

    if count==2:
        print(ans[0]*ans[1])
        exit()


print(0)
H,N = map(int,input().split(" "))
lis = []
lis_append = lis.append
dp = [10**10 for _ in range(H+1)]
for i in range(N):
    a,b = map(int,input().split(" "))
    dp[a] = b
    lis_append([a,b])


for i in range(H+1):
    for a,b in lis:
        if i + a <= H:
            dp[i+a] = min(dp[i+a],dp[i]+b)
        else:
            dp[-1] = min(dp[-1],dp[i]+b)
print(dp[-1])

### FIXED CODE ###

H,N = map(int,input().split(" "))
lis = []
lis_append = lis.append
dp = [2**50 for _ in range(H+1)]
ans = 2**60
for i in range(N):
    a,b = map(int,input().split(" "))
    if a >= H:
        ans = min(ans,b)
    lis_append([a,b])

dp[0] = 0
for i in range(H+1):
    for a,b in lis:
        if i + a <= H:
            dp[i+a] = min(dp[i+a],dp[i]+b)
        else:
            dp[H] = min(dp[H],dp[i]+b)

ans = min(ans,dp[H])
print(ans)
import decimal


def resolve():
    n = int(input())
    A = list(map(decimal.Decimal, input().split()))
    A_sum = sum(A)
    ind_sum = 0
    for a in A:
        ind_sum += a**2

    print((A_sum**2 - ind_sum)//2 % (10**9 + 7))

resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    sm = sum(A) % (10**9 + 7)

    ans = 0
    for a in A:
        sm -= a
        ans += sm * a
        ans %= (10**9 + 7)
    print(ans)

resolve()
# -*- coding: utf-8 -*-

n = int(raw_input())
l = map(int, raw_input().split())
A = [0]
for i in range(n):
    A.append(l[i])
print "node %d: key = %d, left key = %d, right key = %d, " %(1, A[1], A[2*1], A[2*1+1])
for i in range(2, int(n/2+1)):
    print "node %d: key = %d, parent key = %d, left key = %d, right key = %d, " %(i, A[i], A[int(i/2)], A[2*i], A[2*i+1])
for i in range(int(n/2+1), n+1):
    print "node %d: key = %d, parent key = %d, " %(i, A[i], A[int(i/2)])

### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(raw_input())
l = map(int, raw_input().split())
A = [0]
for i in range(n):
    A.append(l[i])
print "node %d: key = %d, left key = %d, right key = %d, " %(1, A[1], A[2*1], A[2*1+1])
for i in range(2, int((n+1)/2)):
    print "node %d: key = %d, parent key = %d, left key = %d, right key = %d, " %(i, A[i], A[int(i/2)], A[2*i], A[2*i+1])
if not n%2:
    i = n/2
    print "node %d: key = %d, parent key = %d, left key = %d, " %(i, A[i], A[int(i/2)], A[2*i])
for i in range(int(n/2)+1, n+1):
    print "node %d: key = %d, parent key = %d, " %(i, A[i], A[int(i/2)])
import numpy as np
import sys

n, m, l = map(int, raw_input().split())
a = []
b = []
for i in range(n):
	a.append(map(int, raw_input().split()))
for i in range(m):
	b.append(map(int, raw_input().split()))

a = np.matrix(a)
b = np.matrix(b)

c = a * b

for i in xrange(n):
	for j in xrange(l-1):
		sys.stdout.write(str(c[i,j])+" ")
	print c[i,l-1]

### FIXED CODE ###

import sys

N, M, L = map(int, raw_input().split())
a = []
b = []
for n in range(N):
	a.append(map(int, raw_input().split()))
for m in range(M):
	b.append(map(int, raw_input().split()))

c = [[0 for l in xrange(L)] for n in xrange(N)]

for n in xrange(N):
	for l in xrange(L):
		for m in xrange(M):
			c[n][l] += a[n][m] * b[m][l]

for n in xrange(N):
	for l in xrange(L-1):
		sys.stdout.write(str(c[n][l])+" ")
	print c[n][L-1]
s = input()
dp = [[1, 0, 0, 0]]
for s in S:
    tmp = [0, 0, 0, 0]
    if s == 'A' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[1] += dp[-1][0]
    if s == 'B' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[2] += dp[-1][1]
    if s == 'C' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[3] += dp[-1][2]
    dp.append(tmp)
print(dp[-1][-1]%(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()