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

import heapq

# def heapify(x):
#     for i in range((x)):
#         x[i] = -x[i]
#     heapq.heapify(x)

# def heappush(heap, item):
#     heapq.heappush(heap, -item)

# def heappop(heap):
#     return -heapq.heappop(heap)

# from heapq import heappop, heappush
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


def raw_input():
    return input()


rooms_count, passages_count = map(int, raw_input().split())
matrix = []
for i in range(0, rooms_count):
    matrix.append([])
    for j in range(0, rooms_count):
        matrix[i].append(False)

for j in range(0, passages_count):
    a, b = map(int, raw_input().split())
    matrix[a - 1][b - 1] = True
    matrix[b - 1][a - 1] = True

seen = set()
distance = [10000] * rooms_count
next = [10000] * rooms_count
h = []
heapq.heappush(h, (0, 0, -1))
while len(h):
    (d, room, parent) = heapq.heappop(h)
    if (distance[room] <= d):
        continue
    distance[room] = d
    next[room] = parent
    seen.add(room)

    for neighbor in range(0, rooms_count):
        if neighbor != room and matrix[room][neighbor]:
            heapq.heappush(h, (d + 1, neighbor, room))

if len(seen) == rooms_count:
    print('Yes')
    for room in range(1, rooms_count):
        print(next[room] + 1)
else:
    print('No')


### FIXED CODE ###

import heapq

# def heapify(x):
#     for i in range((x)):
#         x[i] = -x[i]
#     heapq.heapify(x)

# def heappush(heap, item):
#     heapq.heappush(heap, -item)

# def heappop(heap):
#     return -heapq.heappop(heap)

# from heapq import heappop, heappush
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


def raw_input():
    return input()


rooms_count, passages_count = map(int, raw_input().split())
adj = []
for i in range(0, rooms_count):
    adj.append([])

for j in range(0, passages_count):
    a, b = map(int, raw_input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

seen = set()
distance = [100000000] * rooms_count
next = [100000000] * rooms_count
h = []
heapq.heappush(h, (0, 0, -1))
while len(h):
    (d, room, parent) = heapq.heappop(h)
    if (distance[room] <= d):
        continue
    distance[room] = d
    next[room] = parent
    seen.add(room)

    for neighbor in adj[room]:
        heapq.heappush(h, (d + 1, neighbor, room))

if len(seen) == rooms_count:
    print('Yes')
    for room in range(1, rooms_count):
        print(next[room] + 1)
else:
    print('No')
### BUGGY CODE ###

N = int(input())
A=[]
S=[]
for i in range(N):
    a = list(input())
    a.sort()
    A.append(a)
    if a not in S:
        S.append(a)

count=0
for i in S:
    if A.count(i)==1:
        continue
    count += A.count(i)*(A.count(i)-1)//2
print(count)

### FIXED CODE ###

N = int(input())
A=[]
S={}
for i in range(N):
    a = list(input())
    a.sort()
    b = ''.join(a)
    if b not in S:
        S[b] = 1
    else:
        S[b] += 1


count=0
for i in S.values():
    if i==1:
        continue
    count += i*(i-1)//2
print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]

# 小さい順にソートする
#def sort(h):
#    if len(h) <= 1:
#        return h
#    base = h[-1]
#    low_temp = [];
#    high_temp = [];
#    base_count = 1
#    for i in range(len(h)-1):
#        if h[i] < base:
#            low_temp.append(h[i])
#        elif h[i] > base:
#            high_temp.append(h[i])
#        else:
#            base_count += 1
#    low = sort(low_temp)
#    high = sort(high_temp)
#    return low + [base]*base_count + high

h.sort()
hantei = 10**10
for i in range(N-K+1):
    temp = h[i:i+K]
    if (temp[-1] - temp[0]) < hantei:
        hantei = temp[-1] - temp[0]

print(hantei)


### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))
### BUGGY CODE ###

p=int(input())
k=100
o=0
j=0
while p>k:
    k1=k+(k*101)//10000
    o+=1
print(o)

### FIXED CODE ###

def main(p):
    k=100
    a=0
    while k<p:
        k=(k+k*0.01)//1
        a+=1
    print(a)
p=int(input())   
main(p)
### BUGGY CODE ###

X=int(input())

def f(p, q):
    s=(q-p**4)/5
    if s%1>0:
        return False, None
    
    t=yakusu(s)
    for A in t:
        if A*(A**3-2*p*(A**2)+2*A*(p**2)-p**3)==s:
            if A>=0:
                A=int(A)
            else:
                A=-int(-A)
            B=A-p
            if B>=0:
                B=int(B)
            else:
                B=-int(-B)
            return True, [A, B]
    return False, None

def yakusu(x):
    if x<0:
        x*=-1
    tmp=int(pow(x, 1/2))+1
    out=set()
    for i in range(1, tmp):
        if x%i==0:
            out.add(i)
            out.add(x//i)
    if pow(x, 1/2)%1==0:
        out.add(pow(x, 1/2))
    out=list(out)
    out=out+[-i for i in out]
    out.sort()
    return out

tmp=yakusu(X)
for p in tmp:
    q=X//p
    hantei, ans=f(p, q)
    if hantei==True:
        print(ans[0], ans[1])
        exit()
        
    hantei, ans=f(-p, -q)
    if hantei==True:
        print(ans[0], ans[1])
        exit()
        


### FIXED CODE ###

X=int(input())

for A in range(-10**3, 10**3):
  for B in range(-10**3, 10**3):
    if A**5-B**5==X:
      print(A, B)
      exit()
### BUGGY CODE ###

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

DP = [[10**5 for _ in range(n)] for _ in range(n)]
for i in range(n):
    DP[i][i] = 0

Edge = []
for _ in range(m):
    a, b, c = map(int, input().split())
    DP[a-1][b-1] = c
    DP[b-1][a-1] = c
    Edge.append((a,b,c))

for k in range(n):
    for i in range(n):
        for j in range(n):
            DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j])

Edge_check = [0 for _ in range(len(Edge))]
for e in range(len(Edge)):
    for s in range(n):
        for t in range(n):
            if s == t:
                continue
            i = Edge[e][0] -1
            j = Edge[e][1] -1
            cost = Edge[e][2]
            if DP[s][i] + cost + DP[j][t] == DP[s][t]:
                Edge_check[e] = 1

ans = len(Edge_check) - sum(Edge_check)
print(ans)



### FIXED CODE ###

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

DP = [[10**5 for _ in range(n)] for _ in range(n)]
for i in range(n):
    DP[i][i] = 0

Edge = []
for _ in range(m):
    a, b, c = map(int, input().split())
    DP[a-1][b-1] = c
    DP[b-1][a-1] = c
    Edge.append((a,b,c))

for k in range(n):
    for i in range(n):
        for j in range(n):
            DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j])

Edge_check = [0 for _ in range(len(Edge))]
for e in range(len(Edge)):
    for s in range(n):
        for t in range(n):
            if s == t:
                continue
            i = Edge[e][0] -1
            j = Edge[e][1] -1
            cost = Edge[e][2]
            if DP[s][i] + cost + DP[j][t] == DP[s][t]:
                Edge_check[e] = 1

ans = len(Edge_check) - sum(Edge_check)
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
for i in range(N):
    tmp = A.pop(i)
    print(max(A))
    A.insert(i,tmp)

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
maxind = A.index(max(A))
maxa = max(A)
A = sorted(A)
ans = [maxa]*maxind
ans.append(A[-2])
[ans.append(i) for i in [maxa]*(N-maxind-1)]
print(*ans,sep="\n")
### BUGGY CODE ###

n=int(input())
arr=list(input())
arr=[int(arr[i]) for i in range(n)]
if n==1:
  print(arr[0])
if n==2:
  print(abs(arr[0]-arr[1]))
else:
  tmp=[]
  for i in range(n-2):
    tmp.append(abs(abs(arr[i]-arr[i+1])-abs(arr[i+1]-arr[i+2])))
  arr=tmp
  while len(arr)>3:
    tmp=[]
    if len(arr)%2==9:
      for i in range(len(arr)//2):
        tmp.append(abs(arr[2*i]-arr[2*i+1]))
    else:
      for i in range(len(arr)-1):
        tmp.append(abs(arr[i]-arr[i+1]))
    arr=tmp
  if len(arr)==1:
    print(arr[0])
  elif len(arr)==2:
    print(abs(arr[0]-arr[1]))
  elif len(arr)==3:
    print(abs(abs(arr[0]-arr[1])-abs(arr[1]-arr[2])))

### FIXED CODE ###

n=int(input())
arr=list(input())
arr=[int(arr[i]) for i in range(n)]
if n==1:
  print(arr[0])
if n==2:
  print(abs(arr[0]-arr[1]))
else:
  tmp=[]
  for i in range(n-2):
    tmp.append(abs(abs(arr[i]-arr[i+1])-abs(arr[i+1]-arr[i+2])))
  arr=tmp
  while len(arr)>3:
    tmp=[]
    if len(arr)%2==0:
      for i in range(len(arr)//2):
        tmp.append(abs(arr[2*i]-arr[2*i+1]))
    else:
      for i in range(len(arr)-1):
        tmp.append(abs(arr[i]-arr[i+1]))
    arr=tmp
  if len(arr)==1:
    print(arr[0])
  elif len(arr)==2:
    print(abs(arr[0]-arr[1]))
  elif len(arr)==3:
    print(abs(abs(arr[0]-arr[1])-abs(arr[1]-arr[2])))
### BUGGY CODE ###

numbers = input()

while numbers[1] == numbers[2]:
    if numbers.count(numbers[1]) >= 3:
        print("Yes")
        exit()

print("No")

### FIXED CODE ###

numbers = input()

if numbers[1] == numbers[2]:
    if numbers.count(numbers[1]) >= 3:
        print("Yes")
        exit()

print("No")
### BUGGY CODE ###

K = int(input())

n = 1
s = 9 * 2 ** (n - 1)
while s < K:
    n = n + 1
    s = 9 * 2 ** (n - 1)

result = []


def bianli(currentIndex, currentValue, currentValueStr, maxLevel):
    if currentIndex < maxLevel:

        nextIndex = currentIndex + 1

        result.append(int(currentValueStr))

        bianli(nextIndex, currentValue, "{}{}".format(currentValueStr, currentValue), maxLevel)

        if currentValue == 0:
            nextValue = 1
            bianli(nextIndex, nextValue, "{}{}".format(currentValueStr, nextValue), maxLevel)
        elif currentValue == 9:
            nextValue = 8
            bianli(nextIndex, nextValue, "{}{}".format(currentValueStr, nextValue), maxLevel)
        else:
            nextValue = currentValue + 1
            bianli(nextIndex, nextValue, "{}{}".format(currentValueStr, nextValue), maxLevel)
            nextValue = currentValue - 1
            bianli(nextIndex, nextValue, "{}{}".format(currentValueStr, nextValue), maxLevel)

    else:
        result.append(int(currentValueStr))


bianli(1, 1,"1", n)
bianli(1, 2,"2", n)
bianli(1, 3,"3", n)
bianli(1, 4,"4", n)
bianli(1, 5,"5", n)
bianli(1, 6,"6", n)
bianli(1, 7,"7", n)
bianli(1, 8,"8", n)
bianli(1, 9,"9", n)

print(sorted(result)[K-1])


### FIXED CODE ###

from collections import deque

K = int(input())

def calculate(n):
    q = deque()
    for i in range(1, 10):
        q.append(i)

    result = []

    while len(result) <= n:
        x = q.popleft()
        result.append(x)
        m = x % 10
        if m == 0:
            q.append(x * 10 + m)
            q.append(x*10+ m +1)
        elif m == 9:
            q.append(x*10 + m - 1)
            q.append(x * 10 + m)
        else:
            q.append(x*10 + m - 1)
            q.append(x * 10 + m)
            q.append(x*10 + m + 1)

    print(result[n-1])


calculate(K)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [False for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
count = 0

for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = set()
        indlist.add(p.index(i))
        numlist = set()
        numlist.add(i)
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.add(num)
            indlist.add(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        count += len(numlist & indlist)
    else:
        if (not alr[i]) and p[i] == i:
            count += 1
print(count)
                
    
        

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [False for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append(y)
    xy[y].append(x)
count = 0

for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [i]
        numlist = set()
        numlist.add(i)
        while stack:
            j = stack.pop()
            for k in xy[j]:
                if not alr[k]:
                    alr[k] = True
                    stack.append(k)
                    numlist.add(k)
        indlist = set([p[i] for i in numlist])
        count += len(numlist & indlist)
    else:
        if (not alr[i]) and p[i] == i:
            count += 1
print(count)
### BUGGY CODE ###

# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    max_a = max(a)
    arr = [1] * (max_a + 1)

    for num in a:
        if a.count(num) > 1:
            arr[num] = 0
        for i in range(num*2, max_a+1, num):
            arr[i] = 0

    for i in range(n):
        if arr[a[i]] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time


def main():

    N = int(input())
    A = [int(i) for i in input().split()]
    D = set()
    S = set()
    for i in range(N):
        if A[i] in S:
            D.add(A[i])
        else:
            S.add(A[i])
    M = max(S)
    X = [1 for i in range(M+1)]
    for a in S:
        if a in D:
            X[a] = 0
        for i in range(2*a, M+1, a):
            X[i] = 0
    ans = 0
    for i in range(N):
        if X[A[i]] == 1:
            ans += 1
    print(ans)


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

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter
from bisect import bisect_right

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A, 1):
        idxs[a] = i
    lowers = [0, N + 1]
    ans = 0
    for a, i in enumerate(idxs[1:], 1):
        j = bisect_right(lowers, i)
        l, r = lowers[j - 1], lowers[j]
        lowers.insert(j, i)
        ans += (i - l) * (r - i) * a

    return ans

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A):
        idxs[a] = i
    ll = list(range(N + 1))
    rr = list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        idx = idxs[a]
        l, r = ll[idx], rr[idx]
        ans += (idx - l + 1) * (r - idx + 1) * a
        ll[r + 1] = l
        rr[l - 1] = r

    return ans

print(main())
### BUGGY CODE ###

n = int(input())
As = input().split()
As = [int(A) for A in As]
ss = [0]
sss = 0
for i in range(n):
        sss += As[i]
        ss.append(sss)
ans = 0
for i in range(0, n):
    for j in range(i + 1, n + 1):
        if ss[j] - ss[i] == 0:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
As = input().split()
As = [int(A) for A in As]
ss = [0]
sss = 0
nd = {0: 1}
for i in range(n):
        sss += As[i]
        ss.append(sss)
        if sss in nd:
            nd[sss] += 1
        else:
            nd[sss] = 1
ans = 0
for k in nd:
    if nd[k] > 0:
        ans += (nd[k] * (nd[k] - 1) // 2)
#for i in range(0, n):
#    for j in range(i + 1, n + 1):
#        if ss[j] - ss[i] == 0:
#            ans += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n = int(input())
a = [int(input()) for _ in range(n)]

for _ in range(n):
    tmp = a.pop(0)
    print(max(a))
    a.append(tmp)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n = int(input())
a = [int(input()) for _ in range(n)]
a_max_1 = max(a)
b = sorted(a, reverse=True)
a_max_2 = b[1]

for i in range(n):
    if a[i] == a_max_1:
        print(a_max_2)
    else:
        print(a_max_1)
### BUGGY CODE ###

from fractions import Fraction
import math
N = int(input())
ans = Fraction(4,N)
point = [1,math.floor(N/4)]
for h in range(1,3501):
    h_pro = Fraction(1,h)
    for n in range(1,3501):
        check = ans - h_pro
        n_pro = Fraction(1,n)
        check -= n_pro
        if type(check) == "int":
            if check ==1:
                print(h, end=" ")
                print(n, end=" ")
                print(1)
                exit()
        elif check.numerator == 1:
            print(h, end=" ")
            print(n, end=" ")
            print(check.denominator)
            exit()

### FIXED CODE ###

from fractions import Fraction
import math
N = int(input())
ans = Fraction(4,N)
point = [1,math.floor(N/4)]
for h in range(max(point),3501):
    h_pro = Fraction(1,h)
    check = ans - h_pro
    target = [math.floor(4*h-N/N*h),h]
    for n in range(h,3501):
        check = ans - h_pro
        n_pro = Fraction(1,n)
        check -= n_pro
        if type(check) == "int":
            if check ==1:
                print(h, end=" ")
                print(n, end=" ")
                print(1)
                exit()
        elif check.numerator == 1:
            print(h, end=" ")
            print(n, end=" ")
            print(check.denominator)
            exit()
### BUGGY CODE ###

n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n) if i not in set(bl)]
mod = 1000000007
al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()

    
li = [i for i in l if i>=2]

for i in li:
    al[i] = (al[i-1] + al[i-2])%mod
    if al[i] == 0:
        print(0)
        exit()

print(al[-1])


### FIXED CODE ###

n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n)]
cnt = 0
for num in bl:
    del l[num-cnt]
    cnt +=1
    
mod = 1000000007

al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()
    
li = [i for i in l if i>=2]
for i in li:
    al[i] = al[i-1] + al[i-2]
    if al[i] == 0:
        print(0)
        exit()

print(al[-1]%mod)
### BUGGY CODE ###

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

s = 0
for i in range(1, N+1):
  for j in range(i+1, N+1):
    s += A[i-1]*A[j-1]
    
s = s % (10**9 + 7)
print(s)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
s = 0
for i in range(N):
  s += A[i]
  s %= (10**9+7)
s = s**2
s %= (10**9+7)
 
t = 0
for i in range(N):
  t += (A[i]**2 % (10**9+7))
t %= (10**9+7)
 
ans = (s-t) % (10**9+7)
'''
tmp = (2**1000000005) % (10**9+7)
'''
tmp = 500000004
ans *= tmp
ans %= (10**9+7)
print(ans)
### BUGGY CODE ###


sortsecond = lambda val: val[1]
N, M, Q = map(int, input().split())
l=[]
p=[]
for i in range(M):
    t=input().split()
    l.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=input().split()
    p.append((int(t[0]),int(t[1])))

ans = int(0)
count = int(0)
sumTrain = [[0 for i in range(N+1)] for j in range(N+1)]
ansTrain = [[0 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    sumTrain[l[i][0]][l[i][1]] += 1

for i in range(N):
    for j in range(N):
        for k in range(i,j+1):
            for l in range(k,j+1):
                ansTrain[i+1][j+1] += sumTrain[k+1][l+1]


for i in range(Q):
    ans = ansTrain[p[i][0]][p[i][1]]
    print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N, M, Q = map(int, input().split())
l=[]
p=[]
for i in range(M):
    t=input().split()
    l.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=input().split()
    p.append((int(t[0]),int(t[1])))

ans = int(0)
count = int(0)
sumTrain = [[0 for i in range(N+1)] for j in range(N+1)]
ansTrain = [[-1 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    sumTrain[l[i][0]][l[i][1]] += 1

def dfs(l, r):
    if not l <= r:
        return 0
    if l == r:
        return sumTrain[l][r]
    if ansTrain[l][r] != -1:
        return ansTrain[l][r]
    ansTrain[l][r] = res = sumTrain[l][r] + dfs(l+1, r) + dfs(l, r-1) - dfs(l+1, r-1)
    return res

for i in range(Q):
    ans = dfs(p[i][0],p[i][1])
    print(ans)
### BUGGY CODE ###

import sys
S=sys.stdin.readline()

M=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		ans+=ab
	if x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=M
	ab%=M
	a%=M
	all%M


print ans%M


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

# coding: utf-8

n, m = map(int, input().split())
l = [int(n) for n in input().split()]

for j in range(m):
    i =l.index(max(l))
    l[i] = int(l[i]/2)
print(sum(l))

    

### FIXED CODE ###

# coding: utf-8
import heapq

n, m = map(int, input().split())
l = [ -1 * int(n) for n in input().split()]

heapq.heapify(l)

for i in range(m):
    a = heapq.heappop(l) * (-1)
    a = int(a/2)
    if a != 0:
        heapq.heappush(l, a * (-1))
    if len(l) == 0:
        break
    
    
print(sum(l) * (-1))