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

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
from math import *
input = sys.stdin.readline

def main():
    n = int(input())
    As = list(map(int, input().split()))
    mod = 10**9 + 7

    isp, fac_table = min_factor_table(max(As)+1)
    fac_table = fac_table[:-1]

    prime_factors = defaultdict(int)
    #各素因数の最大値を保持
    for i in range(n):
        pf = factorization(fac_table, As[i])
        for j in pf:
            prime_factors[j] = max(pf[j], prime_factors[j])
    
    lcm = 1
    for key in prime_factors:
        lcm *= pow(key, prime_factors[key])    
    
    ans = 0
    ans = sum([lcm // As[i] for i in range(n)]) % mod

    print(ans)
    return

def factorization(table, n):
    # O(log N )
    k = n
    prime_factors = defaultdict(int)
    while k != 1:
        if k % table[k] == 0:
            prime_factors[table[k]] += 1
            k //= table[k]

    return prime_factors


def min_factor_table(n):
    #多分計算量はO(N log N)
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    min_factor = [None]*(n+1)
    min_factor[0] = 0
    min_factor[1] = 1
    cnt = 0
    # 計算する必要があるのは√n まで
    for i in range(2, n+1):   
        for j in range(2, ceil(n/i)):
            cnt += 1
            if min_factor[i*j] is None:
                min_factor[i*j] = i
            is_prime[i*j] = False
        if is_prime[i]:
            min_factor[i] = i
    return is_prime, min_factor


#参考: https://qiita.com/ophhdn/items/e6451ec5983939ecbc5b
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans



if __name__ == '__main__':
    main()

### FIXED CODE ###

from functools import reduce
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers)
mod = 10**9 + 7
n = int(input())
As = list(map(int, input().split()))

lcm = lcm_list(As)
b = [lcm//As[i] for i in range(n)]

print(sum(b) % mod)
### BUGGY CODE ###

N = int(input())
S = input()        

dic = {"":1}

for c in S:
    dic_tmp = dic.copy()
    for k in dic_tmp:
        if not(c in k):
            dic[k+c] = (dic.get(k+c,0)+dic_tmp[k])%(10**9+7) 
ans = 0     
del dic[""]
for k in dic:
    ans += dic[k]
    ans %= 10**9+7
print(ans)      

### FIXED CODE ###

N = int(input())
S = input()        

tmp = []
for a in "abcdefghijklmnopqrstuvwxyz":      
    tmp.append(S.count(a)+1)
    
ans = 1 
for i in tmp:
    ans = ans * i % (10**9+7)
    
print(ans-1)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    B = list(map(int, input().split()))
    B.sort()
    sum_a = sum(A)
    sum_b = sum(B)
    k = sum_b - sum_a

    now = 0
    while now < N and A[now] == B[now]:
        now += 1

    while k > 0 and now < N:
        while now < N and  A[now] == B[now]:
            now += 1
        
        if now < N:
            A[now] += 2
            B[now] += 1
            k -= 1
            if A[now] == B[now]:
                now += 1
    
    if now == N:
        print("Yes")
    else:
        print("No")
        
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    need = 0
    stock = 0
    for a, b in zip(A, B):
        if a > b: need += (a-b)
        if b > a: stock += (b-a)//2

    if stock >= need:
        print("Yes")
    else:
        print("No")

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

import sys

target = int(input())

list_After = [str(n) for n in range(10)]
list_Before = []

count = 9

while 1:
  list_Before = list_After
  list_After = []
  for i in range(10):
    flag = 0
    for element in list_Before:
      if (abs(i - int(element[0])) >= 2) & (flag == 1):
        break
      elif abs(i - int(element[0])) >= 2:
        continue
      else:
        list_After.append(str(i) + element)
        if i != 0:
          count += 1
          if count == target:
            print(str(i) + element)
            sys.exit()


### FIXED CODE ###

import queue
target = int(input())

q = queue.Queue()

for i in range(1,10):
  q.put(str(i))


for cnt in range(1, target):
  num = q.get()
  mod = int(num) % 10
  
  if mod == 0:
    q.put(num + "0")
    q.put(num + "1")
  elif mod == 9:
    q.put(num + "8")
    q.put(num + "9")
  else:
    q.put(num + str(mod - 1))
    q.put(num + str(mod))
    q.put(num + str(mod + 1))

print(q.get())
### BUGGY CODE ###

def main():
    s = list(map(int, list(input())))
    m = [0]*2019
    num = 0
    ans = 0
    for i, si in enumerate(s[::-1]):
        num += si*10**i
        num %= 2019
        m[num] += 1 
    for mi in m:
        if mi:
            ans += (mi*(mi-1))//2
    ans += m[0]
    print(ans)
        
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = list(map(int, list(input())))
    m = [0]*2019
    num = 0
    ans = 0
    n = len(s)
    ten = 1
    for i in range(n):
        num += s[n-i-1]*ten
        num %= 2019
        m[num] += 1 
        ten = (ten*10)%2019
    for mi in m:
        if mi:
            ans += (mi*(mi-1))//2
    ans += m[0]
    print(ans)
        
if __name__ == "__main__":
    main()
### BUGGY CODE ###

#ABC072-C
import collections
import itertools

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

cnt = 0
a.sort()

for i in range(len(a)):
    tmp = a.count(a[i]-1) + a.count(a[i]) + a.count(a[i]+1)
    if tmp > cnt:
        cnt = tmp
        
print(cnt)


### FIXED CODE ###

#ABC072-C
n = int(input())
a = list(map(int,input().split()))
 
cnt = [0] * 100002


for i in a:
    cnt[i] += 1
    cnt[i+1] += 1
    cnt[i+2] += 1
    
    

    
        
print(max(cnt))
### BUGGY CODE ###

from collections import defaultdict as d
p=d(str)
n=int(input())
print(0, flush = True)
s = input()
if s == "Vacant": exit()
else:
    print(n-1,flush=True)
    t=input()
    if t == "Vacant": exit()
    else:
        p[0]=s
        p[n-1]=t
        l=0
        r=n-1
        while l-r!=1:
            g=(l+r)//2
            if p[l]=="":
                print(l, flush = True)
                s = input()
                p[l]=s
                if s == "Vacant": exit()
                else:
                    s=p[l]
            if p[g]=="":
                print(g, flush = True)
                t = input()
                p[g]=t
                if t == "Vacant": exit()
                else:
                    t=p[g]
            if ((g-l)%2!=0 and s!=t) or ((g-l)%2!=1 and s==t):
                l=g
            else:
                r=g
        if p[l]=="":
            print(l, flush = True)
            s = input()
            p[l]=s
            if s == "Vacant": exit()
        if p[r]=="":
            print(g, flush = True)
            t = input()
            p[r]=t
            if r == "Vacant": exit()

### FIXED CODE ###

from collections import defaultdict as d
p=d(str)
n=int(input())
print(0, flush = True)
s = input()
if s == "Vacant": exit()
else:
    p[0]=s
    p[n]=s
    l=0
    r=n
    while 1:
        g=(l+r)//2
        print(g, flush = True)
        s = input()
        p[g]=s
        if s == "Vacant": break
        else:
            t=p[l]
            if ((g-l)%2!=0 and s!=t) or ((g-l)%2!=1 and s==t):
                l=g
            else:
                r=g
### BUGGY CODE ###

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

mod_number = 10**9 + 7

total = 0
for i in range(0, N - 1):
    for j in range(i + 1, N):
        total += A[i] * A[j]

ans = total % mod_number

print(ans)

### FIXED CODE ###

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

mod_number = 10**9 + 7
sum_A = sum(A)
total = 0
for i in range(0, N - 1):
    sum_A = sum_A - A[i]
    total += A[i] * sum_A

ans = total % mod_number

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

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

c=0

for x in range(s+1):
  for y in range(s+1-x):
    for z in range(s+1-x-y):
      if x>k or y>k or z>k:
        continue
      if x+y+z==s:
        c+=1
print(c)

### FIXED CODE ###

k,s=map(int,input().split())
 
c=0
m=min(s,k)
for x in range(m+1):
  for y in range(m+1):
    if s<x+y:
      break
    elif s>x+y+k:
      continue
    else:
      c+=1
print(c)
### BUGGY CODE ###

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

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

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

### FIXED CODE ###

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

if 0 in A:
    print(0)
    exit()

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

    if r > 10**18:
        print(-1)
        exit()

print(r)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
from math import factorial

def combination_formula(n, r):
    return factorial(n) // (factorial(r)*factorial(n-r))

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    # ai > aj
    # C(ai, aj) とするとき、aiは大きければ大きいほどよいので、Asの最大値でよい
    # 問題はajをどう決めるか。とりあえず全探索？

    As.sort()
    n = As[-1]
    ans_i = 0
    max_c = combination_formula(n, As[0])
    for i in range(1, N-1):
        c = combination_formula(n, As[i])
        if c > max_c:
            max_c = c
            ans_i = i

    print(n, As[ans_i])


if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-
from math import factorial
import bisect


def solve():
    N = int(input())
    As = list(map(int, input().split()))

    # ai > aj
    # C(ai, aj) とするとき、aiは大きければ大きいほどよいので、Asの最大値でよい
    # 問題はajをどう決めるか。
    """
    C(n,r) を毎回計算するのは計算が重い。なので計算させずに済む方法を考える。
    C(n,r) = n! / r!(n-r)! である。今、nはAsの最大値と決まっているので、定数とみなして良い。
    よって、C(n,r)が大きいとは、分子の r!(n-r)!ができるだけ小さいものである。
    r!(n-r)!を全探索で計算するのも処理が重いのでしたくない。
    ところで、n=10のとき、r!(n-r)!を、r = 1 ~ 10まで手書きで書いてみるとわかるが、

    1) 1* 9*8*7*6*5*4*3*2*1
    2) 1*2* 8*7*6*5*4*3*2*1
    3) 1*2*3* 7*6*5*4*3*2*1
    4) 1*2*3*4* 6*5*4*3*2*1
    5) 1*2*3*4*5* 5*4*3*2*1  <-これが一番小さい
    6) 1*2*3*4*5*6* 4*3*2*1  <-これは4)と同じ

    r = n//2のときが一番小さくなるっぽいことがわかる。

    そのようなrを、Asの中から探せば良い。これは二分探索で高速に探せる。
    """

    As.sort()
    n = As[-1]
    i = bisect.bisect_left(As[:-1], n//2)
    if i == 0:
        r = As[0]
    elif i == N-1:
        r = As[N-2]
    else:
        if abs(As[i-1] - n//2) < abs(As[i] - n//2):
            r = As[i-1]
        else:
            r = As[i]

    print(n, r)


if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0]
for i in range(1,n):
  l+=[min(l[i-j]+abs(a[i]-a[i-j])for j in range(1,min(k,i)+1))]
print(l[-1])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0]
for i in range(1,n):
  b=a[i]
  l.append(min(l[j]+abs(b-a[j])for j in range(i-min(k,i),i)))
print(l[-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    edge[u].append(v)
    edge[v].append(u)

ans = [-1] * n
def bfs(p, v):
    dq = deque()
    dq.append((p, v))
    while dq:
        p, v = dq.popleft()
        if ans[v] == -1:
            ans[v] = p
        for nv in edge[v]:
            if nv == p:
                continue
            if ans[nv] == -1:
                dq.append((v, nv))

bfs(-1, 0)
if -1 in ans[1:]:
    print("No")
else:
    print("Yes")
    for item in ans[1:]:
        print(item + 1)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    edge[u].append(v)
    edge[v].append(u)

ans = [-2] * n
def bfs(p, v):
    dq = deque()
    dq.append((p, v))
    while dq:
        p, v = dq.popleft()
        if ans[v] == -1:
            ans[v] = p
        for nv in edge[v]:
            if nv == p:
                continue
            if ans[nv] == -2:
                dq.append((v, nv))
                ans[nv] = -1 

bfs(-1, 0)
if -1 in ans[1:]:
    print("No")
else:
    print("Yes")
    for item in ans[1:]:
        print(item + 1)
### BUGGY CODE ###

from heapq import heapify, heappush, heappop

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    heapify(A)

    for _ in range(M):
        b, c = map(int, input().split())
        for _ in range(b):
            m = heappop(A)
            if m >= c:
                heappush(A, m)
                break
            heappush(A, c)
    
    print(sum(A))


if __name__ == "__main__":
    main()

### FIXED CODE ###

from heapq import heapify, heappush, heappop
from operator import itemgetter

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    heapify(A)

    query = [list(map(int, input().split())) for _ in range(M)]
    query.sort(key=itemgetter(1), reverse=True)

    for b, c in query:
        for _ in range(b):
            m = heappop(A)
            if m >= c:
                heappush(A, m)
                break
            heappush(A, c)
        else:
            continue
        break
    
    print(sum(A))


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

S = input()
Q = int(input())

is_filp = False
for i in range(Q):
    q = input()

    if q[0] == '1':
        if is_filp:
            is_filp = False
        else:
            is_filp = True
    elif q[0] == '2':
        _, f, c = q.split(' ')
        if f == '1':
            if is_filp:
                S = S + c
            else:
                S = c + S 
        else:
            if is_filp:
                S = c + S
            else:
                S = S + c
if is_filp:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

import bisect

S = input()
Q = int(input())

S = {i: s for i, s in enumerate(S)}


head = -1
tail = len(S)

is_filp = False
for i in range(Q):
    q = input()

    if q[0] == '1':
        if is_filp:
            is_filp = False
        else:
            is_filp = True
    elif q[0] == '2':
        _, f, c = q.split(' ')
        if f == '1':
            if is_filp:
                S[tail] = c
                tail += 1
            else:
                S[head] = c
                head -= 1
        else:
            if is_filp:
                S[head] = c
                head -= 1
            else:
                S[tail] = c
                tail += 1

if is_filp:
    print(''.join([S[i] for i in range(tail - 1, head, -1)]))
else:
    print(''.join([S[i] for i in range(head + 1, tail)]))
### BUGGY CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    import math
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    l,r=0,a[-1]
    while math.ceil(r)>math.ceil(l):
        x=(l+r)/2
        cnt=0
        for i in a:
            if i%x==0:
                cnt+=i//x-1
            else:
                cnt+=i//x
        if cnt>k:
            l=x
        else:
            r=x
    print(math.ceil(l))

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    import math
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    l,r=0,a[-1]
    while math.ceil(r)>math.ceil(l):
        x=(l+r)/2
        cnt=0
        for i in a:
            if i%x==0:
                cnt+=i//x-1
            else:
                cnt+=i//x
        if cnt>k:
            l=x
        else:
            r=x
    print(math.ceil(l))

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

#!/usr/bin/env python3

import math
x = int(input())

#aもbも0以上のとき
border = 1;
while border ** 5 - (border - 1) ** 5 < x:
    border += 1

for i in range(border + 1):
    aa = ((x + i ** 5) ** (1.0 / 5.0)) #仮
    if aa % 1 == 0:
        a = int(aa)
        b = i
        print(a, b)
        break
else:
    while True:
        b = -1
        aa = ((x + b ** 5) ** (1.0 / 5.0))  # 仮
        if aa % 1 == 0:
            a = int(aa)
            print(a, b)
            break
        if x + b ** 5 < 0:
            break
        b -= 1




### FIXED CODE ###

#!/usr/bin/env python3

import math
x = int(input())

#aもbも0以上のとき
border = 1;
while border ** 5 - (border - 1) ** 5 < x:
    border += 1

for i in range(border + 1):
    aa = ((x + i ** 5) ** (1.0 / 5.0)) #仮
    a = round(aa)
    if a ** 5 - i ** 5 == x:
        b = i
        print(a, b)
        break
else:
    b = -1

    while x + b ** 5 >= 0:

        aa = ((x + b ** 5) ** (1.0 / 5.0))  # 仮
        a = round(aa)
        if a ** 5 - b ** 5 == x:
            print(a, b)
            break
        b -= 1
### BUGGY CODE ###

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

dp = [float('inf')] * n
dp[0] = 0;

for i in range(1, n):
    distances = range(i - 1, max(i - k, 0) - 1, -1)
    for dis in distances:
        dp[i] = min(dp[i], dp[dis] + abs(steps[i] - steps[dis]))

print(dp[n - 1])


### FIXED CODE ###

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

dp = [0] * n
dp[0] = 0;

for i in range(1, n):
    step_to = steps[i]
    dp[i] = min(
        [
            dp_from + abs(step_to - step_from)
            for dp_from, step_from in zip(
                dp[max(0, i - k):i], steps[max(0, i - k):i])
        ]
    )

print(dp[n - 1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
s = list(input())
lr = [list(map(int,input().split())) for _ in range(q)]
for i in range(q):
  x = [s[j] for j in range(n) if (lr[i][0]-1) <= j <= (lr[i][1]-1)]
  print("".join(x).count("AC"))

### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline
n,q = map(int,input().split())
s = list(input())
lr = [list(map(int,input().split())) for _ in range(q)]
ac = []
for i in range(n-1):
  if s[i] == "A" and s[i+1] == "C":
    ac.append(i)
for i in range(q):
  print(bisect.bisect_left(ac,lr[i][1]-1)-bisect.bisect_left(ac,lr[i][0]-1))
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    A = [int(x) - 1 for x in input().split()]

    way = []
    now = 0
    for _ in range(K):
        if now in way:
            loop_start = way.index(now)
            loop = way[loop_start:]
            K -= len(way[:loop_start])
            now = loop[K % len(loop)]
            break
        way.append(now)
        now = A[now]
    print(now + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    A = [int(x) - 1 for x in input().split()]

    way = []
    seen = [False for _ in [0] * (2 * 10 ** 5 + 1)]
    now = 0
    for _ in range(K):
        if seen[now]:
            loop_start = way.index(now)
            loop = way[loop_start:]
            K -= len(way[:loop_start])
            now = loop[K % len(loop)]
            break
        way.append(now)
        seen[now] = True
        now = A[now]
    print(now + 1)


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

import bisect
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())
now = [A[0]]

for i in range(1, N):
    index = bisect.bisect_left(now, A[i])
    if index == 0:
        now = [A[i]] + now
    else:
        now[index-1] = A[i]
print(len(now))


### FIXED CODE ###

import bisect
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())
now = [-A[0]]

for i in range(1, N):

    index = bisect.bisect_right(now, -A[i])
    if index == len(now):
        now.append(-A[i])
    else:
        now[index] = -A[i]

print(len(now))
### BUGGY CODE ###

def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    s = input()
    ope_num = 0
    index = 0
    a_stock = 0
    b_stock = 0
    s = list(s)
    while index < len(s):
        # print(s)
        # print(index)
        # print(ope_num)
        # print()
        si = s[index]
        if si == "A":
            if b_stock > 0:
                a_stock = 1
            else:
                a_stock = a_stock + 1
            b_stock = 0
        elif a_stock > 0:
            if b_stock == 0 and si == "B":
                b_stock = 1
            elif b_stock > 0 and si == "C":
                ope_num = ope_num + a_stock
                # s[index - 2 - a_stock + 1] = "B"
                # s[index - 1 - a_stock + 1] = "C"
                for i in range(a_stock - 1, -1, -1):
                    s[index - i] = "A"
                index = index - a_stock
                a_stock = 0
                b_stock = 0
            else:
                a_stock = 0
                b_stock = 0
        else:
            a_stock = 0
            b_stock = 0
        index = index + 1
    print(ope_num)

# ABCの数
# ABCの前にあるAの分だけ追加で操作できる
# ABCの後にある(BC)の分だけ追加で操作できる

# Aがあれば覚えておく
# ABCと来たら、それより前側に隣接しているAの回数だけ追加で操作できる
# 見つかったABCをBCAに置き換える
# BCAのAから走査を継続する


### FIXED CODE ###

def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    s = input()
    ope_num = 0
    index = 0
    a_stock = 0
    b_stock = 0
    s = list(s)
    while index < len(s):
        # print(s)
        # print(index)
        # print(ope_num)
        # print()
        si = s[index]
        if si == "A":
            if b_stock > 0:
                a_stock = 1
            else:
                a_stock = a_stock + 1
            b_stock = 0
        elif a_stock > 0:
            if b_stock == 0:
                if si == "B":
                    b_stock = 1
                else:
                    a_stock = 0
                    b_stock = 0
            elif si == "C":
                ope_num = ope_num + a_stock
                # s[index - 2 - a_stock + 1] = "B"
                # s[index - 1 - a_stock + 1] = "C"
                # s[index] = "A"
                # index = index - 1
                a_stock = a_stock
                b_stock = 0
            else:
                a_stock = 0
                b_stock = 0
        else:
            a_stock = 0
            b_stock = 0
        index = index + 1
    print(ope_num)

# ABCの数
# ABCの前にあるAの分だけ追加で操作できる
# ABCの後にある(BC)の分だけ追加で操作できる

# Aがあれば覚えておく
# ABCと来たら、それより前側に隣接しているAの回数だけ追加で操作できる
# 見つかったABCをBCAに置き換える
# BCAのAから走査を継続する
### BUGGY CODE ###

S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1))

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans += (a * c) % mod

print(ans % mod)

### FIXED CODE ###

S = input()
n = len(S)
mod = (10**9 + 7)

dp = [[0] * 4 for _ in range(n + 1)]

dp[n] = [0, 0, 0, 1]
for i in range(n-1, -1, -1):
    if S[i] == '?':
        dp[i][3] =  dp[i+1][3] * 3 % mod
        dp[i][2] = (dp[i+1][2] * 3 + dp[i+1][3]) % mod
        dp[i][1] = (dp[i+1][1] * 3 + dp[i+1][2]) % mod
        dp[i][0] = (dp[i+1][0] * 3 + dp[i+1][1]) % mod
    elif S[i] == 'C':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] = (dp[i+1][2] + dp[i+1][3]) % mod
        dp[i][1] =  dp[i+1][1] % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'B':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] =  dp[i+1][2] % mod
        dp[i][1] = (dp[i+1][1] + dp[i+1][2]) % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'A':
        dp[i][3] =  dp[i+1][3]
        dp[i][2] =  dp[i+1][2]
        dp[i][1] =  dp[i+1][1]
        dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % mod
print(dp[0][0])