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

from math import pow
def get_table():
    table = []
    for i in range(10):
        a = int(pow(10, i))
        table.append(a % 2019)
    return table

table = get_table()
# print(table)

def get_power_2019(idx):
    if (idx < len(table)):
        return table[idx]
    else:
        j = int(idx/2)
        i = idx - j
        return (get_power_2019(i) * get_power_2019(j)) % 2019

s = input()
mod_dict = {}

last_mod = 0
for i in range(len(s)-1, -1, -1):
    current_lowest_digit = int(s[i])
    current_mod = ((current_lowest_digit * get_power_2019(len(s)-1-i))% 2019 + last_mod) % 2019
    if (current_mod not in mod_dict.keys()):
        mod_dict[current_mod] = [i]
    else:
        mod_dict[current_mod].append(i)
    last_mod = current_mod

# print(mod_dict)

count = 0
for k in mod_dict.keys():
    n = len(mod_dict[k])
    count += int(n*(n-1)/2)
    if (k == 0):
        count += n
print(count)

### FIXED CODE ###

from math import pow
def get_table():
    table = []
    for i in range(10):
        a = int(pow(10, i))
        table.append(a % 2019)
    return table

table = get_table()
# print(table)

def get_power_2019(idx):
    if (idx < len(table)):
        return table[idx]
    else:
        j = int(idx/2)
        i = idx - j
        return (get_power_2019(i) * get_power_2019(j)) % 2019

for i in range(10, 10000):
    curr = get_power_2019(i)
    table.append(curr)

s = input()
mod_dict = {}

last_mod = 0
for i in range(len(s)-1, -1, -1):
    current_lowest_digit = int(s[i])
    current_mod = ((current_lowest_digit * get_power_2019(len(s)-1-i))% 2019 + last_mod) % 2019
    if (current_mod not in mod_dict.keys()):
        mod_dict[current_mod] = [i]
    else:
        mod_dict[current_mod].append(i)
    last_mod = current_mod

# print(mod_dict)

count = 0
for k in mod_dict.keys():
    n = len(mod_dict[k])
    count += int(n*(n-1)/2)
    if (k == 0):
        count += n
print(count)
### BUGGY CODE ###

N=int(input())
for n in range(1,N+1):
    ans = 0
    for i in range(1,int(n**0.5)):
        for j in range(i,int(n**0.5)):
            for k in range(j,int(n**0.5)):
                if i**2+j**2+k**2+i*j+j*k+k*i==n:
                    if i == j and j == k:
                        ans += 1
                    else:
                        ans += 3

    print(ans)


### FIXED CODE ###

N=int(input())
ans = [0]*10000000
for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
            ans[i**2+j**2+k**2+i*j+j*k+i*k] += 1
for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	lzero = [0]*62
	lone = [0]*62
	for v in al:
		for i in range(62):
			if v & (2**i) > 0:
				lone[i] += 1
			else:
				lzero[i] += 1
	ret = 0
	for i, (n_one, n_zero) in enumerate(zip(lone, lzero)):
		t = pow(2, i, mod) * n_one * n_zero
		ret += t
		ret %= mod
		
	print(ret)
		
			
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	lzero = [0]*62
	lone = [0]*62
	for v in al:
		for i in range(62):
			if v & (2**i) > 0:
				lone[i] += 1
			else:
				lzero[i] += 1
	ret = 0
	for i, (n_one, n_zero) in enumerate(zip(lone, lzero)):
		t = pow(2, i, mod) * n_one * n_zero
		ret += t
		ret %= mod
		
	print(ret)
		
			
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

num = int(input())

lst = []
pos = [0,0,0,0,0]

for i in range(5):
    lst.append(i)

pos[0] = num
while (pos[0] + pos[1] + pos[2] + pos[3]) != 0:
    if pos[0] != 0:
        if pos[0] >= lst[0]:
            pos[1] += lst[0]
        else:
            pos[1] += pos[0]
    
    if pos[1] != 0:
        if pos[1] >= lst[1]:
            pos[2] += lst[1]
        else:
            pos[2] += pos[1]
    
    if pos[2] != 0:
        if pos[2] >= lst[2]:
            pos[3] += lst[2]
        else:
            pos[3] += pos[2]

    if pos[3] != 0:
        if pos[3] >= lst[3]:
            pos[4] += lst[3]
        else:
            pos[4] += pos[3]
    
print(pos,lst)

### FIXED CODE ###

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
 
min = min(A, B, C, D, E)
 
ans = 4 + int(N/min)
if N % min != 0:
    ans = ans + 1
print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
B = [int(x) for x in input().split()]
A=Counter(B)
V, C = zip(*A.most_common())
count=0
for x in C:
  if x==1:
    break
  count+=x*(x-1)/2
for x in B:
  ans=count-C[V.index(x)]+1
  print(int(ans))

### FIXED CODE ###

from collections import Counter
N = int(input())
B = [int(x) for x in input().split()]
A=Counter(B)
V, C = zip(*A.most_common())
count=0
i=0
dict={}
for x in C:
  count+=x*(x-1)/2
  dict[V[i]]=x
  i+=1
for x in B:
  ans=count-dict[x]+1
  print(int(ans))
### BUGGY CODE ###

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

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = map(int, input().split())
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

sub_size = [[] for _ in range(N)]

def dfs(cur, pre) :
  s = 0
  for nex in vec[cur] :
    if nex == pre :
      continue
    t = dfs(nex, cur)
    s += t
    sub_size[cur].append(t)
  return s + 1

dfs(0, -1)

ret = 0
for i in range(N) :
  if sum(sub_size[i]) != N - 1 :
    sub_size[i].append(N - 1 - sum(sub_size[i]))
  
  if len(sub_size[i]) <= 1 :
    continue

  a, b = 1, 1
  for ss in sub_size[i] :
    x = pow(2, ss, mod)
    a *= pow(x, mod - 2, mod)
    b += x - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * pow(2, mod - 2, mod) % mod

print(ret)

### FIXED CODE ###

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

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = map(int, input().split())
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

own_size = [0] * N
sub_size = [[] for _ in range(N)]

# pythonのdfs重すぎて自分でstack書かないと通らない。
# く〜〜つらいとこね、これ！！！！
stack = [(0, -1)]
for i in range(N) :
  cur, pre = stack[i]
  for nex in vec[cur] :
    if nex != pre :
      stack.append((nex, cur))

while stack :
  cur, pre = stack.pop()
  if pre != -1 :
    sub_size[pre].append(own_size[cur] + 1)
    own_size[pre] += own_size[cur] + 1
  if own_size[cur] != N - 1 :
    sub_size[cur].append(N - 1 - own_size[cur])

fac = [1]
inv = [1]
div = pow(2, mod - 2, mod)
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(inv[-1] * div % mod)

ret = 0
for i in range(N) :
  if len(sub_size[i]) < 2 :
    continue

  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * div % mod

print(ret)
### BUGGY CODE ###

N=int(input())
ls=[int(input()) for _ in range(N)]
color=[ls[-1]]
ans=1
for i in range(N-1):
  a=ls[-2-i]
  for j in range(ans):
    if a<color[j]:
      color[j]=a
      break
  else:
    color.append(a)
    ans+=1
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
ls=[int(input()) for _ in range(N)]
color=[ls[-1]]
ans=1
for i in range(N-1):
  a=ls[-2-i]
  k=bisect.bisect_right(color,a)
  if k==ans:
    color.append(a)
    ans+=1
  else:
    color[k]=a
print(ans)
### BUGGY CODE ###

N = int(input())

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

ans = []
for i in range(1,N+1):
    print(A.index(i)+1,end= " ")
    

### FIXED CODE ###

N = int(input())

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

student = list(range(0,N))

student.sort(key = lambda x:A[x])

for s in student:
    print(s+1,end= " ")
### BUGGY CODE ###

import sys
import numpy as np
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()

#動的計画法 dp
dp =np.array([[0 for j in range(n+1)] for i in range(n+1)])

for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if i <j:
            if S[i] == S[j]:
                dp[i][j] = 1 + dp[i+1][j+1]
                if dp[i][j] >=n/2:
                    dp[i][j] = 0

#print(dp)
print(np.max(dp))

### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1

#print(dp)

for i in range(1, n-1):
    for j in range(i+1, n):
        if S[i] ==S[j]:
            dp[i][j] = min(dp[i-1][j-1] +1, j-i)

maxp = 0
for i in range(n-1):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]
#print(dp)
print(maxp)
### BUGGY CODE ###

import bisect
ans = 0
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
lis_B = [0] * N
for i in range(N):
  tmp = bisect.bisect_right(C, B[i])
  if tmp  == N:
    break
  lis_B[i] = N - tmp
for i in range(N):
  tmp = bisect.bisect_right(B, A[i])
  if tmp == N:
    break
  ans += sum(lis_B[tmp:N])
print(ans)

### FIXED CODE ###

import bisect
ans = 0
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
for i in range(N):
  tmp_1 = bisect.bisect_right(C, B[i])
  tmp_2 = bisect.bisect_left(A, B[i])
  ans += (N - tmp_1) * tmp_2
print(ans)
### BUGGY CODE ###

p = int(input())
b_list = [0 for _ in range(p)]
a_list = list(map(int,input().split()))
if a_list[0] == 1:
    a_list[0] = 0
    b_list[0] = 1
    b_list[p-1] = -1
c = 0
for i in a_list:
    t = i
    for j in range(p-1):
        b_list[p-j-1] -= t
        t = (t*c)%p
    c += 1
for j in b_list:
    print(j % p,end = ' ')


### FIXED CODE ###

p = int(input())
b_list = [0 for _ in range(p-1)]
a_list = list(map(int,input().split()))
def frac(n):
    if a_list[n] == 1:
        t = 1
        for j in range(p-1):
            b_list[j] -= t
            t = (t*n)%p
if a_list[0] == 1:
    b_list[0] -= 1
for i in range(p-1):
    frac(i+1)
b_list.reverse()
print(a_list[0],end = ' ')
for j in b_list:
    print(j % p,end = ' ')
### BUGGY CODE ###

i=j=x=int(input())
while(i:=-~i%99)**5-j**5-x:j=j%257-i
print(i,j)

### FIXED CODE ###

x,r=int(input()),range(-99,120);[i**5-x-j**5or exit(print(i,j))for i in r for j in r]
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

"""
グラフの最短経路問題
１からたどる
最短経路の時，たどる前にいた点を答えとして収納すれば良い
"""
ans = [0] * (N + 1)
neighbor = [[0] * (N+1) for _ in range(N+1)]
for a,b in AB:
    neighbor[a][b] = 1
    neighbor[b][a] = 1

que = deque([1])
while len(que) > 0:
    s = que.popleft()
    for i in range(len(neighbor[s])):
        if neighbor[s][i] == 1 and ans[i] == 0:
            ans[i] = s
            que.append(i)

if 0 not in ans[2:]:
    print("Yes")
else:
    print("No")
    exit()

for i in ans[2:]:
    print(i)

### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

"""
グラフの最短経路問題
１からたどる
最短経路の時，たどる前にいた点を答えとして収納すれば良い
"""
ans = [0] * (N + 1)
neighbor = [[] for _ in range(N+1)]

for a,b in AB:
    neighbor[a].append(b)
    neighbor[b].append(a)

que = deque([1])
while len(que) > 0:
    s = que.popleft()
    
    for i in neighbor[s]:
        if ans[i] == 0:
            ans[i] = s
            que.append(i)

if 0 not in ans[2:]:
    print("Yes")
else:
    print("No")
    exit()

for i in ans[2:]:
    print(i)
### BUGGY CODE ###

from collections import Counter

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

c = Counter(s)

max_count = c.most_common()[0][1]

a = []

for i in range(len(c)):
    if max_count == c.most_common()[i][1]:
        a.append(c.most_common()[i][0])
    else:
        break

b = sorted(a)

for i in range(len(b)):
    print(b[i])

### FIXED CODE ###

from collections import Counter

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

c = Counter(s)

max_count = c.most_common()[0][1]

c = sorted(c.items())

for i in range(len(c)):
    if max_count == c[i][1]:
        print(c[i][0])
### BUGGY CODE ###

n=int(input())
x=[int(i) for i in input().split()]
#print(n,x)
for i in range(n):
  y=x[0:i]+x[i+1:]
#  print(y)
  dist=abs(y[0])
  for j in range(len(y)-1):
    dist+=abs(y[j]-y[j+1])
  dist+=abs(y[-1])
  print(dist)

### FIXED CODE ###

n=int(input())
x=[int(i) for i in input().split()]

dist=abs(x[0])
for i in range(n-1):
  dist+=abs(x[i]-x[i+1])
dist+=abs(x[-1])

print(dist-abs(x[0])-abs(x[0]-x[1])+abs(x[1]))

for i in range(1,n-1):
  if x[i-1]<=x[i]<=x[i+1] or x[i+1]<=x[i]<=x[i-1]:
    print(dist)
  else:
    print(dist-abs(x[i-1]-x[i])-abs(x[i]-x[i+1])+abs(x[i-1]-x[i+1]))

print(dist-abs(x[-1])-abs(x[-1]-x[-2])+abs(x[-2]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
mod=10**9+7

XOR=[0]
for a in A:
    XOR.append(XOR[-1]^a)

ZEROS=[0]
for xor in XOR:
    if xor==0:
        ZEROS.append(ZEROS[-1]+1)
    else:
        ZEROS.append(ZEROS[-1])

if XOR[-1]!=0:
    SUBJ=XOR[-1]
    SUBJ_LIST=[]

    for j in range(N+1):
        if XOR[j]==SUBJ:
            SUBJ_LIST.append(j)

    #print(SUBJ_LIST)

    ZERO=1
    NOW=0

    for i in range(len(SUBJ_LIST)):
        ZERO+=NOW*(ZEROS[SUBJ_LIST[i]]-ZEROS[SUBJ_LIST[i-1]])
        NOW+=ZERO

        #print(NOW,ZERO)

    print(ZERO%mod)

else:
    SET=set(XOR)
    
    from collections import defaultdict
    SUBJ=defaultdict(list)
    for j in range(1,N+1):
        SUBJ[XOR[j]].append(j)

    ANS=1<<(ZEROS[-1]-2)

    for subj in SUBJ:
        if subj==0:
            continue
        ZERO=1
        NOW=0

        for i in range(len(SUBJ[subj])):
            
            ZERO+=NOW*(ZEROS[SUBJ[subj][i]]-ZEROS[SUBJ[subj][i-1]])
            NOW+=ZERO

        #print(ZERO,SUBJ[subj],subj)
        ANS=(ANS+NOW)%mod

    print(ANS%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
mod=10**9+7

XOR=[0]
for a in A:
    XOR.append(XOR[-1]^a)

ZEROS=[0]
for xor in XOR:
    if xor==0:
        ZEROS.append(ZEROS[-1]+1)
    else:
        ZEROS.append(ZEROS[-1])

if XOR[-1]!=0:
    SUBJ=XOR[-1]
    SUBJ_LIST=[]

    for j in range(N+1):
        if XOR[j]==SUBJ:
            SUBJ_LIST.append(j)

    #print(SUBJ_LIST)

    ZERO=1
    NOW=0

    for i in range(len(SUBJ_LIST)):
        ZERO+=NOW*(ZEROS[SUBJ_LIST[i]]-ZEROS[SUBJ_LIST[i-1]])
        NOW+=ZERO

        #print(NOW,ZERO)

    print(ZERO%mod)

else:
    SET=set(XOR)
    
    from collections import defaultdict
    SUBJ=defaultdict(list)
    for j in range(1,N+1):
        SUBJ[XOR[j]].append(j)

    ANS=1<<(ZEROS[-1]-2)

    for subj in SUBJ:
        if subj==0:
            continue
        ZERO=1
        NOW=0

        for i in range(len(SUBJ[subj])):
            
            ZERO=(ZERO+NOW*(ZEROS[SUBJ[subj][i]]-ZEROS[SUBJ[subj][i-1]]))%mod
            NOW=(NOW+ZERO)%mod

        #print(ZERO,SUBJ[subj],subj)
        ANS=(ANS+NOW)%mod

    print(ANS%mod)
### BUGGY CODE ###

#import matplotlib.pyplot as plt

def main():
    a,b,n = map(int,input().split())
    mx = 0
    for x in range(1,min(b+1,n+1)):
        left = int(a*x/b)
        right = a * int(x/b)
        #print("x=",x,"floor(Ax/B)=",int(a*x//b),"A*floor(x/B)=",a * int(x // b),"answer=",left-right)
        #right.append(a * int(x/b))

        mx = max(left-right,mx)
    print(mx)


    #plt.plot(list(range(len(right))),right,label="test")


if __name__ == '__main__':
    main()


### FIXED CODE ###

#import matplotlib.pyplot as plt

def main():
    a,b,n = map(int,input().split())
    x = min(b-1,n)



    print(int(a*x/b) - a * int(x/b))


    #plt.plot(list(range(len(right))),right,label="test")


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

# from collections import deque
from collections import Counter
from scipy.misc import comb
# from scipy.special import comb
from copy import deepcopy

n = int(input())
k = list(map(int, input().split()))
for i in range(len(k)):
    ans = 0
    k_n = deepcopy(k)
    k_n.pop(i)
    c = Counter(k_n)
    for key in c:
        ans += comb(c[key], 2, exact=True)
    print(ans)

### FIXED CODE ###

# from collections import deque
from collections import Counter
from scipy.misc import comb
# from copy import deepcopy

n = int(input())
a = list(map(int, input().split()))
C = Counter(a)
S = 0
for key in C:
    S += comb(C[key], 2, exact=True)

for k in range(n):
    A = a[k]
    print(S - C[A] + 1)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
ans = [0 for _ in range(n)]
l = [0]*q
r = [0]*q
for j in range(q):
    l[j], r[j] = map(int, input().split())

for i in range(len(s)-1):
    if s[i] == "A" and s[i+1] == "C":
        ans[i] = 1
for k in range(q):
    print(sum(ans[l[k] - 1:r[k] - 1]))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ans = [0 for _ in range(n)]
for i in range(len(s) - 1):
    if s[i:i+2] == "AC":
        ans[i+1] = ans[i]+1
    else:
        ans[i+1] = ans[i]
    #1indexの累積和

for j in range(q):
    l, r = map(int, input().split())
    print(ans[r-1]-ans[l-1])
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    graph[r].append((l, i, -d))
    graph[l].append((r, i, d))

check_v = [False for _ in range(n)]
check_e = [False for _ in range(m)]
max_int = 10 ** 10
point = [max_int for _ in range(n)]

for v in range(n):
    Q = deque()
    if not check_v[v]:
        Q.append(v)
    while Q:
        v = Q.popleft()
        for next_v, e, d in graph[v]:                
            if not check_e[e]:
                if point[v] == max_int:
                    point[v] = 0
                if point[next_v] == max_int:
                    point[next_v] = point[v] + d
                else:
                    if point[next_v] != point[v] + d:
                        print('No')
                        exit()
            check_e[e] = True
            if not check_v[next_v]:
                Q.append(next_v)
            check_v[v] = True
print('Yes')


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    graph[r].append((l, r, -d))
    graph[l].append((r, l, d))

max_int = 10 ** 10
point = [None for _ in range(n)]

for v in range(n):
    Q = deque()
    if point[v] is not None:
        continue
    Q.extend(graph[v])
    while Q:
        next_v, v, d = Q.popleft()
        if point[v] is None:
            point[v] = 0
        if point[next_v] is not None:
            if point[next_v] != point[v] + d:
                print('No')
                exit()
            else:
                continue
        point[next_v] = point[v] + d
        Q.extend(graph[next_v])
print('Yes')
### BUGGY CODE ###

N, K=map(int, input().split())
H=list(map(int, input().split()))

if N<=K:
  print(0)
elif K==0:
  print(sum(H))
else:
  for i in range(K):
    
    maxh=max(H)
    H.remove(maxh)
    
  print(sum(H))



### FIXED CODE ###

N, K=map(int, input().split())
H=list(map(int, input().split()))

if N<=K:
  print(0)
elif K==0:
  print(sum(H))
else:
  H=sorted(H)
  print(sum(H[:len(H)-K]))
### BUGGY CODE ###

N, A = map(int, raw_input().split())
x = sorted(map(int, raw_input().split()))

def solve(n):
    mem = {}
    def rec(i, a, d):
        if (i, a, d) in mem:
            return mem[(i, a, d)]
        if i >= N:
            return 0
        if a < x[i]:
            return 0
        if d > n:
            return 0
        if x[i] == a and d == n-1:
            mem[(i, a, d)] = rec(i+1, a, d) + 1
        else:
            mem[(i, a, d)] = rec(i+1, a, d) + rec(i+1, a-x[i], d+1)
        return mem[(i, a, d)]
    return rec(0, n*A, 0)

s = 0
for i in xrange(1, N+1):
    s += solve(i)
print s


### FIXED CODE ###

N, A = map(int, raw_input().split())
a = sorted(map(lambda x:int(x)-A, raw_input().split()))
mem = {}

def rec(p, acm):
    if (p, acm) in mem:
        return mem[(p, acm)]
    if p >= N:
        return 0
    if a[p] > 0 and acm > 0:
        return 0
    mem[(p, acm)] = rec(p+1, acm+a[p]) + rec(p+1, acm)
    if acm+a[p] == 0:
        mem[(p, acm)] += 1
    return mem[(p, acm)]

print rec(0, 0)
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

sum1 = sum(A)
sum2 = 0
for i in range(N-1):
    sum1 -= A[i]
    sum2 += A[i] * sum1
print(sum2 % (10 ** 9 + 7))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = list(input())
# from random import randrange
# s = [["A","B","C","?"][randrange(4)] for _ in range(10**5)]
n = len(s)
MOD = 10**9 + 7

def modpow(a,n,m):
    res = 1
    while n>0:
        if n%2==1:
            res = (res * a) % m
        a = (a*a) % m
        n = n//2
    return res

al = [0]*(n+1)
bl = [0]*(n+1)
cl = [0]*(n+1)
ql = [0]*(n+1)
for i in range(n):
    if s[i]=="A":
        al[i+1] += 1
    elif s[i]=="B":
        bl[i+1] += 1
    elif s[i]=="C":
        cl[i+1] += 1
    else:
        ql[i+1] += 1

    al[i+1] += al[i]
    bl[i+1] += bl[i]
    cl[i+1] += cl[i]
    ql[i+1] += ql[i]

res = 0
for i in range(n):
    if s[i]=="A" or s[i]=="C":
        continue

    res += (al[i]-al[0])*(cl[n]-cl[i+1])*modpow(3,(ql[i]-ql[0] + ql[n]-ql[i+1]),MOD)
    res %= MOD
    res += (al[i]-al[0])*(ql[n]-ql[i+1])*modpow(3,(ql[i]-ql[0] + ql[n]-ql[i+1]-1),MOD)
    res %= MOD
    res += (ql[i]-ql[0])*(cl[n]-cl[i+1])*modpow(3,(ql[i]-ql[0]-1 + ql[n]-ql[i+1]),MOD)
    res %= MOD
    res += (ql[i]-ql[0])*(ql[n]-ql[i+1])*modpow(3,(ql[i]-ql[0]-1 + ql[n]-ql[i+1]-1),MOD)
    res %= MOD
print(int(res))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import unittest

MOD = 10**9 + 7

def func(s):
    abc = "ABC"
    n = len(s)
    dp =[[0 for _ in range(3+1)] for _ in range(n+1)]
    dp[n][3] = 1

    for i in range(n-1,-1,-1):
        for j in range(3,-1,-1):
            if j==3:
                if s[i]=="?":
                    dp[i][j] = (dp[i+1][j]*3)%MOD
                else:
                    dp[i][j] = dp[i+1][j]
            else:
                m1 = 3 if s[i]=="?" else 1
                m2 = 1 if s[i]=="?" or s[i]==abc[j] else 0
                dp[i][j] = ((m1*dp[i+1][j])%MOD + (m2*dp[i+1][j+1])%MOD)%MOD
    return dp[0][0]

class Test(unittest.TestCase):
    def test(self):
        self.assertEqual(func("A??C"), 8)
        self.assertEqual(func("ABCBC"), 3)
        self.assertEqual(func("????C?????B??????A???????"), 979596887
)

if __name__ == '__main__':
    print(func(input()))