Harryxun/stf_run huggingface dataset:
from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = {}
for i in range(N):
    edge_map[i] = deque([])

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


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

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

def dfs_res(idx, parent, diff):
    global res_list
    global counters
    if calculated[i]:
        return res_list[idx]
    res = counters[idx] + diff
    res_list[idx] = res
    calculated[idx] = True
    for child in edge_map[idx]:
        if child == parent:
            continue
        dfs_res(child, idx, res)
    return

dfs_res(0, None, 0)

ans = " ".join([str(i) for i in res_list])
print(ans)


### FIXED CODE ###

from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = [[] for i in range(N)]

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


counters = [0]*N

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

target = [0]
while len(target) > 0:
    t = target.pop()
    calculated[t] = True
    for child in edge_map[t]:
        if calculated[child]:
            continue
        target.append(child)
        res_list[child] += res_list[t]

print(*res_list)
N = int(input())
if N % 2 == 1:
    print("No")
	exit()
S = input()
if S[0:N//2] == S[N//2:]:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N = int(input())
if N % 2 == 1:
    print("No")
    exit()
S = input()
if S[0:N//2] == S[N//2:]:
    print("Yes")
else:
    print("No")
def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            return k>=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            return k>=br(a,ini+dist)-bl(a,ini-dist)
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    ix=sorted([[i,j] for i,j in enumerate(x)],key=lambda x:x[1])
    ans=[0]*q
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))
    k=nn

    for i,ini in ix:
        while check(k)==True:k-=1
        k+=1
        ans[i]=aac[-1]-aac[-k-1]+aac2[-k-1]
    for i in ans:
        print(i)
main()

### FIXED CODE ###

def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            return k>=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            return k>=br(a,ini+dist)-bl(a,ini-dist)
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    ix=sorted([[i,j] for i,j in enumerate(x)],key=lambda x:x[1])
    ans=[0]*q
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))
    k=nn

    for i,ini in ix:
        l=1
        u=k
        while l+1<u:
            med=(l+u)//2
            if check(med):u=med
            else:l=med+1
        if check(l):k=l
        else:k=u
        ans[i]=aac[-1]-aac[-k-1]+aac2[-k-1]
    for i in ans:
        print(i)
main()
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    if x==dw-1 and y==dh-1:
      break
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h and maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):

        qu.append([x+dx[i],y+dy[i]])
        ans[y+dy[i]][x+dx[i]] = ans[y][x]
        if i==0:
          for j in range(-2,3):
            if 0 <= x+dx[i]+j < w and 0 <= y+dy[i]+2 < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]+2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+j,y+dy[i]+2])
              ans[y+dy[i]+2][x+dx[i]+j] = ans[y][x]+1
        elif i==2:
          for j in range(-2,3):
            if 0 <= x+dx[i]+j < w and 0 <= y+dy[i]-2 < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]-2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]-2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+j,y+dy[i]-2])
              ans[y+dy[i]-2][x+dx[i]+j] = ans[y][x]+1
              
        elif i==1:
          for j in range(-2,3):
            if 0 <= x+dx[i]+2 < w and 0 <= y+dy[i]+j < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]+2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+2,y+dy[i]+j])
              ans[y+dy[i]+j][x+dx[i]+2] = ans[y][x]+1
        else:
          for j in range(-2,3):
            if 0 <= x+dx[i]-2 < w and 0 <= y+dy[i]+j < h and maze[y+dy[i]+j][x+dx[i]]=="." and (ans[y+dy[i]-2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+j-2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]-2,y+dy[i]+j])
              ans[y+dy[i]+j][x+dx[i]-2] = ans[y][x]+1


bfs(ans)
print(ans[dh-1][dw-1])
  

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.appendleft([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count+=1
    if count!=4:
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
import math
a,b,c=input().split();
if (math.sqrt(float(a)) + math.sqrt(float(b))) <= math.sqrt(float(c)):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

arr=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
t=int(input())
print(arr[t-1])
a,b = map(int,input().split())
d = a / b
r = a % b
f = float(a) / b
print({},{},{}.format(d,r,f))

### FIXED CODE ###

a,b = map(int,input().split())
d = a // b
r = a % b
f = a / b
print('{0} {1} {2:.5f}'.format(d,r,f))
R = int.input()
G = int.input()
ans = 2 * G - R
print(ans)

### FIXED CODE ###

R = int(input())
G = int(input())
ans = 2 * G - R
print(ans)
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
c=0
l=[]
if m==1 and x.length()==1:
    print("0")
else:
    for i in range(m-1):
        l.append(abs(x[i]-x[i+1]))
    l.sort()
    for i in range(len(l)-n+1):
        c+=l[i]
    print(c)

### FIXED CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
c=0
l=[]
for i in range(m-1):
    l.append(abs(x[i]-x[i+1]))
l.sort()
if len(l)-n+1<=0:
    print("0")
else:
    for i in range(len(l)-n+1):
        c+=l[i]
    print(c)
a, b, c = map(int, input())
if (b-a) == (c-b):
  print('YES')
else:
  print('NO')

### FIXED CODE ###

a, b, c = map(int, input().split())
if (b-a) == (c-b):
  print('YES')
else:
  print('NO')
#input
n, a, b = map(int, input().split())

#output
mod = pow(10, 9) + 7

n_ = pow(10, 9) + 1
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

answer = pow(2, n) - 1 - cmb(n, a) - cmb(n, b)
print(answer % mod)

### FIXED CODE ###

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

#output
mod = pow(10, 9) + 7

def cmb(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    k = min(n-k,k)
    value = 1
    inv = [1] * (k+1)
    if k >= 1:
        value *= (n-k+1) % mod
    for i in range(2,k+1):
        inv[i] = mod-inv[mod%i]*(mod//i)%mod
        value = value * (n-k+i) * inv[i] % mod
    return value

answer = (pow(2, n, mod) - 1 - cmb(n, a) - cmb(n, b)) % mod
print(answer % mod)
x = int(input())
y = int(input())
print((x-1)*(y-1))

### FIXED CODE ###

x,y=map(int,input().split())
print((x-1)*(y-1))
import math
A, B, C, D = map(int, input().split())


E = C * D // math.gcd(C, D)

X = (B//C - (A-1)//C)
Y = (B//D - (A-1)//D)
Z = (B//E - (A-1)//E)


print(B - (X+Y-Z)-A + 1)


### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())
E = (C * D) // fractions.gcd(C, D)
print(B - ((B//C - (A-1)//C) + (B//D - (A-1)//D)-(B//E - (A-1)//E))-A + 1)
n, a, b = map(int, input().split())
t = 'b' * a + 'r' * b
count = int(n/len(t)) if (len(t) > 0) else 0
if count == 0:
	t = ''
else:
	count = count + 1
	t=(t*count)[0:n]
print(t.count('b'))


### FIXED CODE ###

n, a, b = map(int, input().split())
t = a + b
count = t if t > 0 else 0
r = 0
if count == 0:
	r = 0
else:
	d = int(n/t)
	if d*t == n:
		r = d * a
	else:
		r = d * a
		e = n - d*t
		if e <= a:
			r = r + e
		else:
			r = r + a
print(r)
N, K = map(int, input().split())
A = list(map(int, input().split()))
passlist = [0]*N
point = 1
depth = 0
waylist = []
while passlist[point-1] == 0:
    passlist[point-1] = 1
    point = A[point-1]
    waylist.append(point)
    depth+=1
print(waylist[depth-K%depth])

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
passlist = [0]*N
point = 1
depth = 0
waylist = []
while passlist[point-1] == 0:
    waylist.append(point)
    passlist[point-1] = depth
    point = A[point-1]
    depth+=1
roop = waylist[waylist.index(point):len(waylist)]
firstreach = passlist[roop[0]-1]
if K < firstreach:
  print(passlist.index(K)+1)
else:
  print(roop[(K-firstreach)%len(roop)])
N = input()
sum = 0
f = 0
for k in range(1,N):
  for j in range(1,k):
  	if k % j == 0：
    	sum += k
print(f)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n + 1):
    y = n // i
    ans += y * (y + 1) * i // 2
print(ans)
N = int(input())
li = list(map(int, input().split()))
li_2 = []

if N == 1:
    print(0)
else:
   for i in range(min(li),max(li)+1):
       cost_sum = 0
       for t in range(N):
           cost_sum += (li[t]-i) ** 2
       li_2.append(cost_sum)
print(min(li_2))


### FIXED CODE ###

N = int(input())
li = list(map(int, input().split()))
li_2 = []

if N == 1:
    print(0)
else:
   for i in range(min(li),max(li)+1):
       cost_sum = 0
       for t in range(N):
           cost_sum += (li[t]-i) ** 2
       li_2.append(cost_sum)
   print(min(li_2))
length = int(input())
s = input()

if s[:length // 2] == s[length // 2:]:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

Ax, Ay, Bx, By = map(int, input().split())
x = Ax - Bx
y = Ay - By

print(Bx + y, By - x, Ax + y, Ay - x)
n=int(input())
a=[]
for i in range(n):
  a.append(int(input()))
print(max(a)-min(a))

### FIXED CODE ###

input()
a=[]
a=list(map(int,input().split()))
print(max(a)-min(a))
from collections import defaultdict
d = defaultdict(list)

N, M = map(int, input().split())
for _ in range(M):
    s, c = map(int, input().split())
    d[s].append(c)

ans = [-1] * N

# とりあえず桁を確定させる
for k, v in d.items():
    if len(set(v)) > 1:
        print(-1)
        exit()
    ans[k - 1] = v[0]

if N == 1:
    val = ans.pop()
    val = max(0, val)
else:
    val = ""
    for i, a in enumerate(ans):
        if a != -1:
            val += str(a)
        else:
            if i == 0:
                val += "1"
            else:
                val += "0"

if val[0] == "0":
    print(-1)
    exit()

print(val)


### FIXED CODE ###

from collections import defaultdict
d = defaultdict(list)

N, M = map(int, input().split())
for _ in range(M):
    s, c = map(int, input().split())
    d[s].append(c)

val = [-1] * N

# とりあえず桁を確定させる
for k, v in d.items():
    if len(set(v)) > 1:
        print(-1)
        exit()
    val[k - 1] = v[0]

if N == 1:
    ans = max(0, val.pop())
    print(ans)
    exit()
if N >= 2:
    if val[0] == 0:
        print(-1)
        exit()

    if val[0] == -1:
        val[0] = 1
    for i in range(N):
        val[i] = max(0, val[i])

    print(*val, sep="")
#

import sys
input=sys.stdin.readline

MOD=10**9+7
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    kl=[0]*(10**6+1)
    for j in range(N):
        n=A[j]
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                if kl[i]<cnt:
                    kl[i]=cnt
        if n!=1:
            if kl[n]<1:
                kl[n]=1
                
    lcm=1
    for i in range(2,10**6+1):
        lcm*=i**kl[i]
        lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
from fractions import gcd
input=sys.stdin.readline

def main():
    MOD=10**9+7
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    l=(A[0]*A[1])//gcd(A[0],A[1])
    for i in range(2,N):
        l=(l*A[i])//gcd(A[i],l-A[i])
    l%=MOD
    ans=0
    for i in range(N):
        ans+=l*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()
import random

X,N = input().split()
X,N = int(X),int(N)

P = input().split()
P = [int(c) for c in P]

if len(P) == 0:
    print(X)    
else:
    L = list(range(max(0,X-N),min(101,X+N)))

    if X+N <= 100:
        L.append(X+N)

    for i in range(N):
        if P[i] in L:
            L.remove(P[i])

    #print(L)

    while len(L) > 2:
        rand = random.randint(1,len(L)-2)
        if L[rand] == X:
            break
        elif L[rand] > X:
            L = L[0:rand+1]
        else:
            L = L[rand:len(L)]

    if X in L:
        print(X)
    else:
        if abs(L[0]-X) > abs(L[1]-X):
            print(L[1])
        else:
            print(L[0])

### FIXED CODE ###

import random

X,N = input().split()
X,N = int(X),int(N)

P = input().split()
P = [int(c) for c in P]

if len(P) == 0:
    print(X)    
else:
    L = list(range(max(0,X-N),min(102,X+N)))

    if X+N <= 101:
        L.append(X+N)

    for i in range(N):
        if P[i] in L:
            L.remove(P[i])

    while len(L) > 2:
        rand = random.randint(1,len(L)-2)
        if L[rand] == X:
            break
        elif L[rand] > X:
            L = L[0:rand+1]
        else:
            L = L[rand:len(L)]

    if X in L:
        print(X)
    elif len(L) == 1:
        print(L[0])
    else:
        if abs(L[0]-X) > abs(L[1]-X):
            print(L[1])
        else:
            print(L[0])
w,a,b=map(int,input().split())
if a<=b<=(a+w) or b<=(a+w)<=(b+w):
  print(0)
elif (a+w)<b:
  print(b-(a+w))
else:
  print(abs(a-(b+w))

### FIXED CODE ###

w,a,b=map(int,input().split())
if a<=b<=(a+w) or b<=(a+w)<=(b+w):
  print(0)
elif (a+w)<b:
  print(b-(a+w))
else:
  print(abs(a-(b+w)))
import fraction
a,b=map(int,input().split())
print((a*b)//fraction.gcd(a,b))

### FIXED CODE ###

import fractions
a,b=map(int,input().split())
print((a*b)//fractions.gcd(a,b))
import numpy as np
n=int(input())
m=np.floor(np.sqrt(n))

l=[]
for i in range(1,m+1,1):
    if n%i==0:
        a=i+(n/i)
        l.append(a)
        
c=int(min(l))
print(c-2)


### FIXED CODE ###

import numpy as np
n=int(input())
m=int(np.ceil(np.sqrt(n)))+1
l=[]

for i in range(1,m,1):
    if n%i==0:
        a=i+(n/i)
        l.append(a)
        
c=int(min(l))
print(c-2)
n, k = map(int, input().split())
a = list(map(int, input().split()))

route ={1}
cur = 1
for i in range(k):
    goto = a[cur - 1]
    x = len(route)
    route.add(goto)
    y = len(route)
    if x == y:
        route = list(route)
        pre_goto = route.index(goto)
        dif = len(route) - pre_goto
        rest_step = (k - pre_goto) % dif
        print(route[pre_goto + rest_step])
        break
    cur = goto
else:
    print(route[k])



### FIXED CODE ###

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

route ={1}
cur = 1
for i in range(k):
    goto = a[cur - 1]
    x = len(route)
    route.add(goto)
    y = len(route)
    if x == y:
        route = list(route)
        pre_goto = route.index(goto)
        dif = len(route) - pre_goto
        rest_step = (k - pre_goto) % dif
        print(route[pre_goto + rest_step])
        break
    cur = goto
else:
    route = list(route)
    print(route[k])
import sys

N=int(input())
for i in range(1,10):
  if N/i==N//i and N/i<10:
    print("Yes")
    sys.exit()
  else:
    print("No")

### FIXED CODE ###

A,B=map(int, input().split())

if A>=10 or B>=10:
 print("-1")
else:
 print(A*B)
h , w = map(int,input().split())
a = [''] * h 
for i in range(n):
    a[i] = input()

row = [False]*h
col = [False]*w

for i in range(h):
    for j  in range(w):
        if a[i][j] =='#':
            row[i] = True
            col[j] = True

for i  in range(h):
    if row[i]:
        for j in range(w):
            if col[j]:
                print(a[i][j],end='')
        print()

### FIXED CODE ###

h , w = map(int,input().split())
a = [''] * h 
for i in range(h):
    a[i] = input()

row = [False]*h
col = [False]*w

for i in range(h):
    for j  in range(w):
        if a[i][j] =='#':
            row[i] = True
            col[j] = True

for i  in range(h):
    if row[i]:
        for j in range(w):
            if col[j]:
                print(a[i][j],end='')
        print()
N = input()
A = input().split()

for i in range(int(N-1)):
  print(A.count(str(i+1)))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = [0] * (n+1)

for a in A:
    B[a] += 1

print('\n'.join(map(str, B[1:])))
import math
H = int(input())
n = math.floor(math.log2(H))
c = 1
for i in range(n):
    c += (2 ** (i+1))
print(c)


### FIXED CODE ###

import math
H = int(input())
n = math.floor(math.log(H, 2))
c = 1
for i in range(n):
    c += (2 ** (i+1))
print(c)
def solve(n, a, b, c):

    b_count = [0]*len(b)
    for i, x in enumerate(b):
        b_count[i] = len(c) - find_ge(c, x)

    ans = 0
    for i in a:
        x = find_ge(b, i)
        ans += sum(b_count[x:])
        
    return ans

if __name__ == "__main__":
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    b = sorted([int(i) for i in input().split()])
    c = sorted([int(i) for i in input().split()])
    print(solve(n, a, b, c))

### FIXED CODE ###

import bisect
import itertools
def find_ge(a, x):
    i = bisect.bisect_right(a,x)
    return i

def solve(n, a, b, c):

    tmp = len(c)
    b_count =list(itertools.accumulate([tmp - find_ge(c, x) for x in b]))
    ans = 0
    for i in a:
        min_index = find_ge(b, i)
        
        ans += b_count[-1] -(0 if min_index == 0 else b_count[min_index-1])
    
    return ans

if __name__ == "__main__":
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    b = sorted([int(i) for i in input().split()])
    c = sorted([int(i) for i in input().split()])
    print(solve(n, a, b, c))
# -*- coding: utf-8 -*-

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・Bの位置を決めて左右パターンを全部数え上げる。
"""

MOD = 10 ** 9 + 7
S = input()

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # kよりも左にあるAの個数
        a = S[:i].count('A')
        # kよりも左にある?の個数
        lq = S[:i].count('?')
        # kよりも右にあるCの個数
        c = S[i+1:].count('C')
        # kよりも右にある?の個数
        rq = S[i+1:].count('?')

        # (A,B,C) と選ぶ場合(後ろの3**lq * 3**rqは使わなかった?の分)
        case1 = a* c * 3**lq * 3**rq
        # (A,B,?) と選ぶ場合
        case2 = a * rq * 3**lq * 3**(rq-1)
        # (?,B,C) と選ぶ場合
        case3 = lq * c * 3**(lq-1) * 3**rq
        # (?,B,?) と選ぶ場合
        case4 = lq * rq * 3**(lq-1) * 3**(rq-1)

        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(int(ans))


### FIXED CODE ###

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

"""
参考：http://drken1215.hatenablog.com/entry/2018/08/05/224100_1
・文字列DP
・こういう、ちょっと状況込み入ったDPがまだ自分でうまく書けない。
・もっと数こなして経験積まなきゃなー。
"""

MOD = 10 ** 9 + 7
S = input()

# 文字列Sのi文字目まで考えたときにABCのj文字目まで照合させた個数
dp = [[0] * 4 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    # i文字目でABCカウントを進めない場合(真下に送る分)
    for j in range(4):
        if S[i] == '?':
            dp[i+1][j] = (dp[i+1][j] + dp[i][j] * 3) % MOD
        else:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
    # i文字目でABCカウントを進める場合(右下に送る分)
    if S[i] == '?' or S[i] == 'A':
        dp[i+1][1] = (dp[i+1][1] + dp[i][0]) % MOD
    if S[i] == '?' or S[i] == 'B':
        dp[i+1][2] = (dp[i+1][2] + dp[i][1]) % MOD
    if S[i] == '?' or S[i] == 'C':
        dp[i+1][3] = (dp[i+1][3] + dp[i][2]) % MOD

print(dp[len(S)][3])
a = []
for i in range(3)
	a.append(Input())
o = a[0,0] + a[1,1] + a[2,2]
print(o)

### FIXED CODE ###

a = []
for i in range(3):
   	a.append(input())
o = a[0][0] + a[1][1] + a[2][2]
print(o)
from collections import deque

s = input()
d = deque()
for i in s:
    d.append(i)
q = int(input())
for i in range(q):
    data = input().split()
    if len(data) == 1:
      if len(d) != 1:
        tmp1 = d.pop()
        tmp2 = d.popleft()
        d.appendleft(tmp1)
        d.append(tmp2)
      else:
        f = int(data[1])
        c = data[2]
        if f == 1:
          d.appendleft(c)
        else:
          d.append(c)
            
s = list(d)
s = "".join(s)
print(s)

### FIXED CODE ###

from collections import deque

s = input()
d = deque()
header = 1
for i in s:
    d.append(i)
q = int(input())
for i in range(q):
        data = input().split()
        if len(data) == 1 :
            header *= -1
        else:
            f = int(data[1])
            c = data[2]
            if header == 1:
                if f == 1:
                    d.appendleft(c)
                else:
                    d.append(c)
            else:
                if f == 1:
                    d.append(c)
                else:
                    d.appendleft(c)
                
if header == -1:
    d.reverse()

s = list(d)
s = "".join(s)



print(s)
A = input()
if A = 1:
  print("Hello world")
if A = 2:
  B = int(input())
  C = int(input())
  print(A+B)
  
  
  

### FIXED CODE ###

A = int(input())
if A == 1:
  print("Hello World")
if A == 2:
  B = int(input())
  C = int(input())
  print(B + C)
a = input()
if "AC" in a:
 print("Yes")
elif:
 print("No")

### FIXED CODE ###

a = input()
if "AC" in a:
 print("Yes")
else:
 print("No")
a,b = map(int,input().split())

import math
print((a*b)//math.gcd(a,b))

### FIXED CODE ###

a,b = map(int,input().split())
import fractions
print((a*b)//fractions.gcd(a,b))
N=int(input())
B=list(map(int,input().split()))
A=[0]*N
for i in range(N-1):
  if B[i]<B[i+1]:
    A[i]+=B[i],A[i+1]+=B[i],A[i+2]+=B[i+1]
  elif B[i]>B[i+1]:
    A[i]+=B[i],A[i+1]+=B[i+1],A[i+2]+=B[i+1]
  else:
    A[i]+=B[i],A[i+1]+=B[i],A[i+2]+=B[i]
print(sum(A))

### FIXED CODE ###

N=int(input())
B=list(map(int,input().split()))
A=[0]*N
A[0]=B[0]
A[N-1]=B[N-2]
for i in range(1,N-1):
  A[i]=min(B[i-1],B[i])
print(sum(A))