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

# https://atcoder.jp/contests/abc159/submissions/11096062
# 写経

def main():
    MOD = 998244353

    NOT_OPENED = 0
    ONGOING = 1
    CLOSED = 2

    N, S = map(int, input().split())
    *A, = map(int, input().split())

    dp = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1

    for i in range(N):
        for s in range(S + 1):
            dp[i + 1][s][NOT_OPENED] += dp[i][s][NOT_OPENED]
            dp[i + 1][s][ONGOING] += dp[i][s][NOT_OPENED] + dp[i][s][ONGOING]
            dp[i + 1][s][CLOSED] += dp[i][s][NOT_OPENED] + dp[i][s][ONGOING] + dp[i][s][CLOSED]

            ps = s - A[i]
            if ps >= 0:
                dp[i + 1][s][ONGOING] += dp[i][ps][NOT_OPENED] + dp[i][ps][ONGOING]
                dp[i + 1][s][CLOSED] += dp[i][ps][NOT_OPENED] + dp[i][ps][ONGOING]

            dp[i + 1][s][NOT_OPENED] %= MOD
            dp[i + 1][s][ONGOING] %= MOD
            dp[i + 1][s][CLOSED] %= MOD

    print(dp[N][S][CLOSED])


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


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

# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N, K = zz()
A = zz()
hyouka = [1] * (N)
mul_A = [1]*(N+1)
mul_A[0] = 1
# mul_A[1] = A[0]
for i in range(N):
    mul_A[i] *= mul_A[i-1]*A[i]

for i in range(K - 1, N):
    # print(mul_A[i], mul_A[i-K])
    hyouka[i] = mul_A[i]//mul_A[i-K]


# print(hyouka[K-1:])
prev = hyouka[K-1]
for now in hyouka[K:]:
    if (prev < now):
        print('Yes')
    else:
        print('No')
    prev = now


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N, K = zz()
A = zz()

for i in range(K, N):
    # print(i, i-K)
    if (A[i] > A[i - K]):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import operator as o
import functools as f
a,b=map(int,input().split())
c=f.reduce(o.mul,range(a,b+1))
if c>0:
  print("Positive")
elif c<0:
  print("Negative")
else:
  print("Zero")

### FIXED CODE ###

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

if a>0:
  print("Positive")
elif 0 in range(a,b+1):
  print("Zero")
else:
  if (b-a)%2==0:
    print("Negative")
  else:
    print("Positive")
### BUGGY CODE ###

import sys
MOD=10**9+7

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

abi=[0]*61
aze=[0]*61

for item in a:
    j=0
    #print(bin(item))
    while j<len(str(bin(item)))-2:
        #print(j)
        if item>>j & 1:
            abi[j]+=1
        else:
            aze[j]+=1
        j+=1
    k=len(str(bin(item)))-2
    while k<61:
        aze[k]+=1
        k+=1


        #print(abi)

result=0
i=0
while i<61:
    result+=(2**i)%MOD*abi[i]*(aze[i])%MOD

    i+=1

#print(abi[:4])

#print(aze[:4])
print(result%MOD)


"""
01
10
11
"""



"""
0001
0010
0011
0100
0101
0110
0111
"""

### FIXED CODE ###

import sys
MOD=10**9+7

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

abi=[0]*61
aze=[0]*61

for item in a:
    j=0
    #print(bin(item))
    while j<61:
        #print(j)
        if item>>j & 1:
            abi[j]+=1
        else:
            aze[j]+=1
        j+=1

        #print(abi)

result=0
i=0
while i<61:
    result+=(2**i)%MOD*abi[i]%MOD*(aze[i])%MOD

    i+=1

#print(abi[:4])

#print(aze[:4])
print(result%MOD)


"""
01
10
11
"""



"""
0001
0010
0011
0100
0101
0110
0111
"""
### BUGGY CODE ###

N, b, r = map(int, input().split())
b_tmp, r_tmp = b, r
ans = 0
for i in range(N):
    if b_tmp:
        ans += 1
        b_tmp -= 1
    elif r_tmp:
        r_tmp -= 1
    if b_tmp or r_tmp:
        pass
    else:
        b_tmp, r_tmp = b, r
print(ans)

### FIXED CODE ###

N, b, r = map(int, input().split())
ans = N // (b + r) * b
N = N % (b + r)
if b > N:
    ans += N
else:
    ans += b
print(ans)
### BUGGY CODE ###

s=input()
mod=10**9+7
retnum={"?":0,"A":1,"B":2,"C":3}
count=[[0 for i in range(len(s))] for j in range(4)]
for i in range(len(s)):
    for j in range(4):
        if retnum[s[i]] == j:
            count[j][i]=count[j][i-1]+1
        else:
            count[j][i]=count[j][i-1]
ans=0
for i in range(1,len(s)-1):
    if s[i]=="B" or s[i]=="?":
        ans+=((3**(max(0,count[0][i-1]-1)))*count[0][i-1]+(3**count[0][i-1])*count[1][i-1])*(3**(max(0,count[0][-1]-count[0][i]-1))*(count[0][-1]-count[0][i])+(3**(count[0][-1]-count[0][i]))*(count[3][-1]-count[3][i]))
        ans%=mod
print(ans)

### FIXED CODE ###

s=input()
mod=10**9+7
retnum={"?":0,"A":1,"B":2,"C":3}
count=[[0 for i in range(len(s))] for j in range(4)]
for i in range(len(s)):
    for j in range(4):
        if retnum[s[i]] == j:
            count[j][i]=count[j][i-1]+1
        else:
            count[j][i]=count[j][i-1]
ans=0
g=[1]*100002
for i in range(1,100002):
    g[i]=g[i-1]*3
    g[i]%=mod
for i in range(1,len(s)-1):
    if s[i]=="B" or s[i]=="?":
        ans+=(g[max(0,count[0][i-1]-1)]*count[0][i-1]+g[count[0][i-1]]*count[1][i-1])*(g[max(0,count[0][-1]-count[0][i]-1)]*(count[0][-1]-count[0][i])+g[count[0][-1]-count[0][i]]*(count[3][-1]-count[3][i]))
        ans%=mod
print(ans)
### BUGGY CODE ###

li = list(map(int,input().split()))
a=li[0]
b=li[1]
k=li[2]
i = 1
while i <= k:
    if a >= 1:
        a = a-1
    elif b >= 1:
        b = b-1
    else:
        break
    i += 1


print(str(a)+" "+str(b))

### FIXED CODE ###

li = list(map(int,input().split()))
a=li[0]
b=li[1]
k=li[2]
if a<k:
    if b<k-a:
        a=0
        b=0
    else:
        b=b-k+a
        a=0
        
else:
    a=a-k

print(str(a)+" "+str(b))
### BUGGY CODE ###

# atcoder DPまとめ
# D_Knapsack1

def get_inputs():
    [n, w] = [int(x) for x in input().split()]
    g = []
    for _ in range(n):
        g.append([int(x) for x in input().split()])
    
    return n, w, g


if __name__ == "__main__":
    
    n, w, g = get_inputs()
    
    # dp[i][w]はi-1個目の品物を加えるか吟味した後、重さw以下で最大の価値
    dp = [[0] * (w + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for wgt in range(w + 1):
            if wgt >= g[i -1][0]:
                dp[i][wgt] = max(dp[i - 1][wgt - g[i - 1][0]] + g[i - 1][1], dp[i - 1][wgt])
            else:
                dp[i][wgt] = dp[i - 1][wgt]
    
    print(max(dp[n]))

### FIXED CODE ###

def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]
 
num, capacity = map(int, input().split())
print(calc(num,capacity))
### BUGGY CODE ###

import numpy as np
from numba import njit

N = int(input())
scores = np.array(list(map(int, input().split())), dtype='int64')

@njit('i8(i8[:],i8,i8)', cache=True)
def get_max_score(scores, i, j):
    if i == j:
        return scores[i]
    return max(scores[i] - get_max_score(scores, i+1, j), scores[j] - get_max_score(scores, i, j-1))

print(get_max_score(scores, 0, len(scores)-1))


### FIXED CODE ###

import numpy as np
from numba import njit

N = int(input())
scores = np.array(list(map(int, input().split())), dtype='int64')
dpt = np.full((N, N), -10**18, dtype='int64')

@njit('i8(i8[:],i8[:,:],i8,i8)', cache=True)
def get_max_score(scores, dpt, i, j):
    if i == j:
        dpt[i][j] = scores[i]
        return scores[i]
    else:
        if dpt[i][j] != -10**18:
            return dpt[i][j]
        result = max(scores[i] - get_max_score(scores, dpt, i+1, j), scores[j] - get_max_score(scores, dpt, i, j-1))
        dpt[i][j] = result
        return result

print(get_max_score(scores, dpt, 0, len(scores)-1))
### BUGGY CODE ###

import numpy as np
n=int(input())
a=list(map(int,input().split()))
sign=[1 if i%2==0 else -1 for i in range(n)]
a=np.array(a)
sign=np.array(sign)
plusA=a*sign
minusA=a*sign*-1
# print(plusA,minusA)
for i in range(n):
    if i%2==0:
        # print(minusA[:i],plusA[i:])
        print(np.sum(minusA[:i])+np.sum(plusA[i:]),end=' ')
    else:
        # print(plusA[:i],minusA[i:])
        print(np.sum(plusA[:i])+np.sum(minusA[i:]),end=' ')


### FIXED CODE ###

import numpy as np
n=int(input())
a=list(map(int,input().split()))
sign=[1 if i%2==0 else -1 for i in range(n)]
a=np.array(a)
sign=np.array(sign)
plusA=a*sign
# minusA=a*sign*-1
ruisekiPlusA=[0 for i in range(n+1)]
for i in range(1,n+1):
    ruisekiPlusA[i]=ruisekiPlusA[i-1]+plusA[i-1]

# print(plusA,minusA)
for i in range(n):
    if i%2==0:
        # print(minusA[:i],plusA[i:])
        # print(np.sum(minusA[:i])+np.sum(plusA[i:]),end=' ')
        print(ruisekiPlusA[n]-2*ruisekiPlusA[i],end=' ')
    else:
        # print(plusA[:i],minusA[i:])
        # print(np.sum(plusA[:i])+np.sum(minusA[i:]),end=' ')
        print(2*ruisekiPlusA[i]-ruisekiPlusA[n],end=' ')
### BUGGY CODE ###

s = input()
mod = 10**9 + 7
abc = 0
bc = 0
c = 0
q = 0
for i in reversed(s):
  if i == "A":
    abc = (abc + bc) % mod
  if i == "B":
    bc = (bc + c) % mod
  if i == "C":
    c = (3**q+c) % mod
  if i == "?":
    abc = (abc*3 + bc) % mod
    bc = (bc*3 + c) % mod 
    c = (3**q + c*3) % mod
    q += 1
print(abc)


### FIXED CODE ###

s = input()
mod = 10**9 + 7
abc = 0
bc = 0
c = 0
q = 0
for i in s[::-1]:
  if i == "A":
    abc = (abc + bc) % mod
  if i == "B":
    bc = (bc + c) % mod
  if i == "C":
    c = (pow(3,q,mod) + c) % mod
  if i == "?":
    abc = (abc*3 + bc) % mod
    bc = (bc*3 + c) % mod 
    c = (pow(3,q,mod) + c*3) % mod
    q += 1
print(int(abc))
### BUGGY CODE ###


import sys

s1 = input()
s2 = input()

n1 = 0
t1 = 0

for i1 in range(len(s2) ):
    t1 =  s1.find(s2[i1])
    if t1 == -1:
        print(t1)
        sys.exit()
    n1 += t1 + 1
    s1 = s1[t1 + 1:] + s1[0:t1 + 1]

print(n1)

### FIXED CODE ###

import sys

s1 = input()
s2 = input()

n1 = 0
t1 = 0
t2 = -1

for i1 in range(len(s2) ):
    t1 =  s1.find(s2[i1],t2 + 1)
    if t1 == -1:
        t1 = s1.find(s2[i1], 0, t2 + 1)
        if t1 == -1:
            print(t1)
            sys.exit()
        else:
            n1 += t1 + (len(s1) - t2)
    else:
        n1 += t1 - t2
    t2 = t1

print(n1)
### BUGGY CODE ###

import collections

n = int(input())
s = []
for i in range(n):
    ss = input()
    s.append(collections.Counter(list(ss)))
ans = 0
for i in range(len(s)):
    for j in range(i + 1, len(s)):
        if s[i] == s[j]:
            ans += 1
print(ans)

### FIXED CODE ###

import collections
import math

n = int(input())
s = []
for i in range(n):
    ss = input()
    s.append(tuple(sorted(collections.Counter(list(ss)).items())))
s = sorted(s)

ans = []
px = None
a = 0
for x in s:
    if x == px:
        a += 1
    else:
        px = x
        if a > 0:
            ans.append(a + 1)
        a = 0
if a > 0:
    ans.append(a + 1)
print(sum([math.factorial(a) // (2 * math.factorial(a - 2)) for a in ans]))
### BUGGY CODE ###

from heapq import heappush, heappop

N, M, Start, Goal = map(int, input().split())
Start -= 1
Goal -= 1
adj_list = [[] for _ in range(N)]
for i in range(M):
  u, v, yen, sunuke = map(int, input().split())
  u -= 1
  v -= 1
  adj_list[u].append([u, v, yen, sunuke])
  adj_list[v].append([v, u, yen, sunuke])

def dijkstra(start, changed):
  res = [ -1 for _ in range(N) ]
  q = [[0, start]]
  visited = {}

  while len(q)>0:
    money, city = heappop(q)
    if res[city]>=0:
      continue
    res[city] = money

    for from_city, to_city, yen, sunuke  in adj_list[city]:
      cost = sunuke if changed else yen
      heappush(q, [money+cost, to_city])
        

  return res


min_yen_path = dijkstra(Start, False)
min_sunuke_path = dijkstra(Goal, True)

res = []
max_sunuke = 0
for i in reversed(range(N)):
  s = 10**15-min_yen_path[i]-min_sunuke_path[i]
  max_sunuke = max([s, max_sunuke]) 
  res.append(max_sunuke)
  
for i in reversed(res):
  print(i)


### FIXED CODE ###

from heapq import heappush, heappop

N, M, Start, Goal = map(int, input().split())
Start -= 1
Goal -= 1
adj_list = [[] for _ in range(N)]
for i in range(M):
  u, v, yen, sunuke = map(int, input().split())
  u -= 1
  v -= 1
  adj_list[u].append([u, v, yen, sunuke])
  adj_list[v].append([v, u, yen, sunuke])

def dijkstra(start, changed):
  res = [ -1 for _ in range(N) ]
  q = [[0, start]]
  visited = {}

  while len(q)>0:
    money, city = heappop(q)
    if res[city]>=0:
      continue
    res[city] = money

    for from_city, to_city, yen, sunuke  in adj_list[city]:
      if res[to_city]<0:
        cost = sunuke if changed else yen
        heappush(q, [money+[yen, sunuke][changed], to_city])
        

  return res


min_yen_path = dijkstra(Start, 0)
min_sunuke_path = dijkstra(Goal, 1)

res = []
max_sunuke = 0
for i in reversed(range(N)):
  s = 10**15-min_yen_path[i]-min_sunuke_path[i]
  max_sunuke = max([s, max_sunuke]) 
  res.append(max_sunuke)
  
for i in reversed(res):
  print(i)
### BUGGY CODE ###

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
l=[True]*n
sort = sorted(a)


for i in range(n):
  #print(sort[i], l)
  if l[i:] == [False]*len(sort[i:]):
    break
  if l[i] == False:
    continue
  
  for ii in range (i+1,n):
    #print(sort[ii])
    if sort[ii] % sort[i] == 0:
      #print("割り切れる")
      l[ii] = False
    if sort[ii] == sort[i]:
      #print("重複")
      l[i] = False
      l[ii] = False

print(len([x for x in l if x]))
      


### FIXED CODE ###

from collections import Counter
max_=10**6+1
ans=0

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

b=[True]*(max_+1)
data.sort()
c=Counter(data)
#print(c)

for d in data:
    if b[d]:
        for j in range(d,max_,d):
            b[j]=False
        if c[d]==1:#複数存在考慮
            ans+=1
print(ans)
### BUGGY CODE ###

a,b,x = map(int, input().split())
num = 0
for i in range(a,b+1):
    if i%x == 0:
        num += 1
print(num)

### FIXED CODE ###

a,b,x = map(int, input().split())
if a%x == 0:
    print(b//x-a//x+1)
else:
    print(b//x-a//x)
### BUGGY CODE ###

h, w, k = map(int, input().split())

r_n = [0] * h
c_n = [0] * w
bomb_table = set()
for i in range(k):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    r_n[hi] += 1
    c_n[wi] += 1
    bomb_table.add((hi, wi))

max_x = max(c_n)
max_y = max(r_n)
ans = max_x + max_y

for i in range(h):
    if r_n[i] != max_y:
        continue
    for j in range(w):
        if c_n[j] != max_x:
            continue
        if (i, j) not in bomb_table:
            print(ans)
            exit(0)

print(ans - 1)


### FIXED CODE ###

h, w, k = map(int, input().split())

r_n = [0] * h
c_n = [0] * w
bomb_table = set()
for i in range(k):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    r_n[hi] += 1
    c_n[wi] += 1
    bomb_table.add((hi, wi))

max_x = max(c_n)
max_y = max(r_n)
ans = max_x + max_y

max_x_table = set()
max_y_table = set()

for i in range(h):
    if r_n[i] == max_y:
        max_y_table.add(i)

for i in range(w):
    if c_n[i] == max_x:
        max_x_table.add(i)

for i in max_y_table:
    for j in max_x_table:
        if (i, j) not in bomb_table:
            print(ans)
            exit(0)
print(ans - 1)
### BUGGY CODE ###

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

MOD = 10**9+7

sum_num = 0
for i in range(60):
    o = 0
    for a in A:
        o += (a>>i)%2
    z = N - o
    sum_num = (sum_num + (o*z)*(1<<i)) % MOD

print(sum_num)

### FIXED CODE ###

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

MOD = 10**9+7

sum_num = 0
for i in range(60):
    o = 0
    for a in A:
        o += (a>>i)%2
    z = N - o
    sum_num = (sum_num + (o*z)*(1<<i)) % MOD

print(sum_num)
### BUGGY CODE ###

def fun(a,k): ## k different steps can be taken
    if len(a)==1:
        return 0
    dp = [float('inf')]*len(a)
    dp[0]=0
    dp[1]=dp[0]+abs(a[0]-a[1])
    for i in range(2,len(a)):
        for j in range(1,min(k+1,i+1)):
            dp[i]=min(dp[i] , dp[i-j]+abs(a[i]-a[i-j]))
    return dp[-1]


from sys import stdin , stdout
n,k = map(int , stdin.readline().split())
a = list(map(int , stdin.readline().split()))
print(fun(a,k))

### FIXED CODE ###

def fun(a,k,n): ## k different steps can be taken
    if n==1:
        return 0
    dp = [0]*n
    dp[1]=dp[0]+abs(a[0]-a[1])
    for i in range(2,len(a)):
        t = 0
        min_ = float('inf')
        for j in range(i-1,-1,-1):
            if t==k:
                break
            else:
                t+=1
            if dp[j]+abs(a[i]-a[j]) < min_ :
                   min_ = dp[j]+abs(a[i]-a[j])
        dp[i]=min_
    return dp[-1]
from sys import stdin , stdout
n,k = map(int , stdin.readline().split())
a = list(map(int , stdin.readline().split()))
print(fun(a,k,n))
### BUGGY CODE ###

input();a=sorted(map(int,input().split()));z=1
for i in a:z*=i
if z>1e18:z=-1
print(z)

### FIXED CODE ###

n,*a=map(int,open(0).read().split());z=1
for i in a:
 if i>1e18//z:z=-1;break
 z*=i
print(0 if 0in a else z)
### BUGGY CODE ###

s=input()
len_s=len(s)
mod=10**9+7
dp=[[0]*13 for i in range(len_s)]

if s[-1]!='?':
    dp[0][int(s[-1])%13]=1
else:
    for i in range(10):
        dp[0][i]=1

for i in range(1,len_s):

    if s[-(i+1)]!='?':
        temp_S=int(s[-(i+1)])
        for j in range(13):
            dp[i][(temp_S*10**i+j)%13]=(dp[i][(temp_S*10**i+j)%13]+dp[i-1][j])%mod

    else:
        for k in range(10):
            for l in range(13):
                dp[i][(k*10**i+l)%13]=(dp[i][(k*10**i+l)%13]+dp[i-1][l])%mod
#print(*dp,sep='\n')
print(dp[-1][5]%mod)


### FIXED CODE ###

s=input()
len_s=len(s)
mod=10**9+7
dp=[[0]*13 for i in range(len_s)]

if s[-1]!='?':
    dp[0][int(s[-1])%13]=1
else:
    for i in range(10):
        dp[0][i]=1

a=1
for i in range(1,len_s):
    a=10*a%13
    if s[-(i+1)]!='?':
        temp_S=int(s[-(i+1)])
        amari=(temp_S*a)%13
        for j in range(13):
            dp[i][(amari+j)%13]+=dp[i-1][j]%mod

    else:
        for k in range(10):
            amari=(k*a)%13
            for l in range(13):
                dp[i][(amari+l)%13]+=dp[i-1][l]%mod
#print(*dp,sep='\n')
print(dp[-1][5]%mod)
### BUGGY CODE ###

import math

k = int(input())

sum_ = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            sum_ += math.gcd(i, math.gcd(j, k))
print(sum_)

### FIXED CODE ###

k = int(input())
from math import gcd
sum_ = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            sum_ += gcd(i, gcd(j, k))
print(sum_)
### BUGGY CODE ###

def C(n, r ,mod=10**9+7):
    if n-r<r: r=n-r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k]) %mod

    return result % mod

A=list(input())
n=len(A)
mod=10**9+7
ans=0
numa= A[0]=="A" 
numa_= A[0]=="?"
numc=A[2:].count("C")
numc_= A[2:].count("?")

for i in range(1,n-1):
    #print(numa,numa_,numc,numc_)
    apro=cpro=0
    if A[i]=="B" or A[i]=="?":
        for k in range(numa_+1):
            apro+= (((C(numa_,k)*pow(2,numa_-k,mod))%mod)*(numa+k))%mod
        for k in range(numc_+1):
            cpro+= (((C(numc_,k)*pow(2,numc_-k,mod))%mod)*(numc+k))%mod
        #print(apro,cpro)
        ans+= (apro*cpro)%mod
        ans%=mod
    if A[i] == "A":
        numa+=1
    if A[i]=="?":
        numa_+=1
    if A[i+1] =="C":
        numc-=1
    if A[i+1]=="?":
        numc_-=1
print(ans)

### FIXED CODE ###

# def C(n, r ,mod=10**9+7):
#     if n-r<r: r=n-r
#     if r == 0: return 1
#     if r == 1: return n
# 
#     numerator = [n - r + k + 1 for k in range(r)]
#     denominator = [k + 1 for k in range(r)]
# 
#     for p in range(2,r+1):
#         pivot = denominator[p - 1]
#         if pivot > 1:
#             offset = (n - r) % p
#             for k in range(p-1,r,p):
#                 numerator[k - offset] /= pivot
#                 denominator[k] /= pivot
# 
#     result = 1
#     for k in range(r):
#         if numerator[k] > 1:
#             result *= int(numerator[k]) %mod
# 
#     return result % mod

A=list(input())
n=len(A)
mod=10**9+7
ans=0
numa= A[0]=="A" 
numa_= A[0]=="?"
numc=A[2:].count("C")
numc_= A[2:].count("?")

for i in range(1,n-1):
    #print(numa,numa_,numc,numc_)
    apro=cpro=0
    if A[i]=="B" or A[i]=="?":
        # for k in range(numa_+1):
        #     apro+= (((C(numa_,k)*pow(2,numa_-k,mod))%mod)*(numa+k))%mod
        # for k in range(numc_+1):
        #     cpro+= (((C(numc_,k)*pow(2,numc_-k,mod))%mod)*(numc+k))%mod
        #print(apro,cpro)
        apro= ((3*numa+numa_)*pow(3,(numa_-1),mod))%mod
        cpro= ((3*numc+numc_)*pow(3,(numc_-1),mod))%mod
        ans+= (apro*cpro)%mod
        ans%=mod
    if A[i] == "A":
        numa+=1
    if A[i]=="?":
        numa_+=1
    if A[i+1] =="C":
        numc-=1
    if A[i+1]=="?":
        numc_-=1
print(ans)