Harryxun/stf_run huggingface dataset:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = sum(A)
for i in Q:
  b,c = map(int, input().split())
  cnt = 0
  while b in A:
    A.remove(b)
    A.append(c)
    cnt += 1
  ans += (c-b) * cnt
  
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = sum(A)
C = Counter(A)

for i in range(Q):
  b, c = map(int, input().split())
  if C[b] != 0:
    cnt = C[b]
    C[c] += cnt
    C[b] = 0
    ans += (c-b) * cnt
  print(ans)
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):
 
    if valid(i,j)==0 or a[i][0][j]=='#':
        return 0
    if i==h-1 and j==w-1:
        return 1

    if dp[i][j]==-1:
           a1=0
           a1+=paths(i+1,j)%m
           a1+=paths(i,j+1)%m
           dp[i][j]=a1%m
           return dp[i][j]
    else:
            return dp[i][j]



h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(1000)]for _ in range(1000)]
print(paths(0,0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)

def paths(i, j):

    if i == h - 1 and j == w - 1:
        return 1
    if a[i][0][j] == '#':
        return 0
    if i < h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j) + paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i == h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i < h - 1 and j == w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j)
            return dp[i][j]
        else:
            return dp[i][j]


h, w = map(int, input().split())
a = [[] for _ in range(h)]
m = 1000000007
for i in range(h):
    a[i].append(input())
dp = [[-1 for _ in range(1000)] for _ in range(1000)]
print(paths(0, 0) % m)
A,B = map(int,input().split())
count = 0
for i in range(1,B):
    if count == 0 and A == B:
        count = 1
        a = 1
        break
    if (A-1)*(i-1)+A >= B:
        a = i
        break
print(a)

### FIXED CODE ###

A, B = map(int, input().split())
cnt = 1
while A*cnt-(cnt-1) < B:
  cnt +=1
print(cnt if B > 1 else 0)
h,w = map(int,input().split())
s = [list("."+input()+".") for _ in range(w)]
s=["."*(w+2)]+s+["."*(w+2)]
flg = 0
for i in range(h):
  for j in range(w):
    if s[i][j] == "#":
      if s[i-1][j]=="." and s[i+1][j]=="." and s[i][j-1]=="." and s[i][j+1]==".":
        flg = 0
print("Yes" if flg == 0 else "No")
    

### FIXED CODE ###

h,w = map(int,input().split())
s = [list("."+input()+".") for _ in range(h)]
s=["."*(w+2)]+s+["."*(w+2)]
flg = 0
for i in range(h):
  for j in range(w):
    if s[i][j] == "#":
      if s[i-1][j]=="." and s[i+1][j]=="." and s[i][j-1]=="." and s[i][j+1]==".":
        flg = 1
print("Yes" if flg == 0 else "No")
print("Yes" if sum([int(input()) == x * y for x in range(1, 10) for y in range(1, 10)]) else "No")

### FIXED CODE ###

print("Yes") if int(input()) in [i*j for i in range(1, 10) for j in range(1, 10)] else print("No")
import heapq
N, L = map(int, raw_input().split())
hq = []
for _ in xrange(N:
    s = raw_input()
    heapq.heappush(hq, s)
ans = ''
while len(hq) > 0:
    ans += heapq.heappop(hq)
print ans

### FIXED CODE ###

import heapq
N, L = map(int, raw_input().split())
hq = []
for _ in xrange(N):
    s = raw_input()
    heapq.heappush(hq, s)
ans = ''
while len(hq) > 0:
    ans += heapq.heappop(hq)
print ans
n, k = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*1001
B[1] = 1
for i in range(2, 1001):
    B[i] = B[i-1] + 0.5
ans = 0
for i in range(n-(n-k)):
    t = 0
    for j in range(k):
        t+=B[A[i+j]]
    ans = max(ans, t)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
B = [(1+i)/2 for i in A]
ans = sum(B[:k])
t = ans
for i in range(n-k):
    t-=B[i]
    t+=B[i+k]
    if t>ans: ans=t
print(ans)
n, k, x, y = map(int, input().split())

if n <= k:
    print(n * x)
else:
    print(k * x + (n - k) * y)

    

### FIXED CODE ###

N = int(input())   
K = int(input())   
X = int(input())    
Y = int(input())    

if N <= K:
    print(N * X)
else:
    print(K * X + (N - K) * Y)
N = int(input())
S = [input() for i in range(N)]

ac = S.count('AC')
wa = S.count('WA')
tle = S.count('TLE')
re = S.count('RE')

print('AC x',ac())
print('WA x',wa)
print('TLE x',tle)
print('RE x',re)

### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]

ac = S.count('AC')
wa = S.count('WA')
tle = S.count('TLE')
re = S.count('RE')

print('AC x',ac)
print('WA x',wa)
print('TLE x',tle)
print('RE x',re)
a=int(input())
b=int(input())
h=int(input())

print(((a+b)＊h)//2)

### FIXED CODE ###

a=int(input())
b=int(input())
h=int(input())
 
print(((a+b)*h)//2)
s = input()
k = int(input())
for i in (len(s)):
    if s[i] != "1":
        ans = int(s[i])
        break
print(ans)

### FIXED CODE ###

s = input()
k = int(input())
ans = 1
if k <= len(s):
    if s[:k] == "1" * k:
        ans = 1
    else:
        for i in range(len(s)):
            if s[i] != "1":
                ans = int(s[i])
                break
else:
    for i in range(len(s)):
        if s[i] != "1":
            ans = int(s[i])
            break
print(ans)
h, w = map(int, input().split())
if h%3 == 0 or w%3 ==0:
    print(0)
else:
    def calculate_t(x, y):
        d = h*w + 1
        i = x//2
        s1, s2 = 0, d
        rng = range(x) if x < 1000 else range(x//3, x*4//5)
        new_d = h*w
        for i in rng:
            s1 = (y//2)*i
            s2 = y*(x-i)
            s3 = (y-y//2)*i
            new_d = max(s1,s2,s3)- min(s1,s2,s3)
            if d > new_d:
                d = new_d
                continue
            else:
                break
        return d
    def calculate_3(x, y):
        h1 = y//3
        h2 = y//3 + y%3
        return x*(h2-h1)
    
    if h == w:
        print(min(d1,d2))
    else:
        d3 = calculate_t(w, h)
        d4 = calculate_3(w, h)
        print(min(d1,d2,d3,d4))

### FIXED CODE ###

h, w = map(int, input().split())
def calculate_t(x, y):
    min_d = 1e12
    for i in range(x):
        s1 = (y//2)*i
        s2 = y*(x-i)
        s3 = (y-y//2)*i
        min_d = min(min_d, max(s1,s2,s3) - min(s1,s2,s3))
    return min_d
def calculate_3(x, y):
    min_d = 1e12
    for i in range(x):
        w1 = i
        w2 = (x-i)//2
        w3 = x - w1 -w2
        min_d = min(min_d, (max(w1,w2,w3)-min(w1,w2,w3))*y)
    return min_d
if (h*w)%3 == 0:
    print(0)
else:
    d1 = calculate_t(h,w)
    d2 = calculate_t(w,h)
    d3 = calculate_3(h,w)
    d4 = calculate_3(w,h)
    print(min(d1,d2,d3,d4))
N, K, X, H = [int(input()) for i in range(4)]
print(X*K+Y*(N-K))

### FIXED CODE ###

N, K, X, Y = [int(input()) for i in range(4)]
print(X*K+Y*(N-K) if N-K > 0 else X*N)
inf = 10**9
H, N = map(int, input().split())
AB = [[0, 0] for i in range(N)]
for i in range(N):
    AB[i][0], AB[i][1] = map(int, input().split())
AB.sort()
T = [[inf for i in range(H+1)] for j in range(N)]
for i in range(N):
    T[i][0] = 0
    if i == 0:
        for j in range(1, H+1):
            if j % AB[i][0] > 0:
                T[i][j] = AB[0][1] * (j // AB[0][0] + 1)
            else:
                T[i][j] = AB[0][1] * (j // AB[0][0])
    else:
        for j in range(1, H+1):
            T[i][j] = min(T[i-1][j], T[i][j - AB[i][0]]+AB[i][1])
print(T[-1][-1])

### FIXED CODE ###

inf = 10**9
H, N = map(int, input().split())
AB = [[0, 0] for i in range(N)]
for i in range(N):
    AB[i][0], AB[i][1] = map(int, input().split())
AB.sort()
T = [[inf for i in range(H+1)] for j in range(N)]
for i in range(N):
    T[i][0] = 0
    if i == 0:
        for j in range(1, H+1):
            if j % AB[i][0] > 0:
                T[i][j] = AB[0][1] * (j // AB[0][0] + 1)
            else:
                T[i][j] = AB[0][1] * (j // AB[0][0])
    else:
        for j in range(1, min(AB[i][0], H+1)):
            T[i][j] = min(T[i-1][j], AB[i][1])
        for j in range(AB[i][0], H+1):
            T[i][j] = min(T[i-1][j], T[i][j - AB[i][0]]+AB[i][1])
print(T[N-1][H])
import sys
n = int(sys.stdin.readline())
p = [int(i) for i in sys.stdin.readline().split()]

if p == sorted(p):
    print('YES')
else:
    swap_index = []
    for i, v in enumerate(p[:-1]):
        if v > p[i + 1]:
            if len(swap_index) == 0:
                swap_index.append(i)
            else:
                swap_index.append(i + 1)
                break
    if len(swap_index) == 1:
        print('NO')
    p[swap_index[0]], p[swap_index[1]] = p[swap_index[1]], p[swap_index[0]]

    if p == sorted(p):
        print('YES')
    else:
        print('NO')


### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
p = [int(i) for i in sys.stdin.readline().split()]

if p == sorted(p):
    print('YES')
elif len(p) == 2:
    print('YES')
else:
    swap_index = []
    for i, v in enumerate(p[:-1]):
        if v > p[i + 1]:
            if len(swap_index) == 0:
                swap_index.append(i)
            else:
                swap_index.append(i + 1)
                break
    if len(swap_index) == 1:
        print('NO')
    else:
        p[swap_index[0]], p[swap_index[1]] = p[swap_index[1]], p[swap_index[0]]
        if p == sorted(p):
            print('YES')
        else:
            print('NO')
H,N = int(input())
A = list(map(int, input().split()))
if sum(A)>=H:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

H,N = map(int,input().split())
A = list(map(int, input().split()))
if sum(A)>=H:
    print("Yes")
else:
    print("No")
n, y = map(int, input().split())
for i in range(0, n+1):
  for j in range(0, n+1-a):
    k = n - i - j
    if 10000 * i + 5000 * j + 1000 * k == y:
      print(i, j, k)
      exit()
print(-1, -1, -1)


### FIXED CODE ###

n, y = map(int, input().split())
for i in range(0, n+1):
  for j in range(0, n+1-i):
    k = n - i - j
    if 10000 * i + 5000 * j + 1000 * k == y:
      print(i, j, k)
      exit()
print(-1, -1, -1)
A = list(map(int, input().split())) 
N = A[0]
K = A[1]
Q = A[2]
n = [K for _ in range(N)]
for i in range(N):
    N[i] -= Q
for _ in range(Q):
    ans = int(input()) - 1
    N[ans] += 1
for i in range(N):
    if(n[i] > 0):
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

A = list(map(int, input().split())) 
N = A[0]
K = A[1]
Q = A[2]
n = [K for _ in range(N)]
for i in range(N):
    n[i] -= Q
for _ in range(Q):
    ans = int(input()) - 1
    n[ans] += 1
for i in range(N):
    if(n[i] > 0):
        print("Yes")
    else:
        print("No")
s=input()
k=int(input())

cnt=0 #1の個数
i=0
while True:
    if s[i]!='1': break
    else:
        cnt+=1
        i+=1
        
print(1 if k<=cnt else s[cnt])

### FIXED CODE ###

s=input()
k=int(input())

cnt=0 #1の個数
i=0
while True:
    if s[i]!='1': break
    else:
        cnt+=1
        i+=1
        if i>len(s)-1: break
        
print(1 if k<=cnt else s[cnt])
n=int(input())
s=input()
k=int(input)
for i in range(n):
  if s[i]!=s[k-1]:
    s[i]=*
print(s)

### FIXED CODE ###

n=int(input())
s=input()
k=int(input())
a=[]
for i in range(n):
  if s[i]!=s[k-1]:
    print("*",end="")
  else: print(s[i],end="")
n = int(input())
ans = ''
for i in range(30):
    if n == 0:
        break
    if n % 2 ** (i + 1) == 0: 
        ans = ans + '0'
    else:
        n -= (-2)**i
        ans = ans + '1'
print(int(ans))

### FIXED CODE ###

n = int(input())
ant = 0
if n == 0:
    ant = 1
ans = ''
for i in range(10000):
    if n == 0:
        break
    if n % 2 ** (i + 1) == 0: 
        ans = '0' + ans
    else:
        n -= (-2)**i
        ans = '1' + ans
if ant == 0:
    print(ans)
else:
    print('0')
H,W,M = map(int,input().split())
h = [0]*M
w = [0]*M

from collections import defaultdict
counter_h = defaultdict(int)
counter_w = defaultdict(int)

for i in range(M):
    h[i],w[i] = map(int, input().split())
    counter_h[h[i]] += 1
    counter_w[w[i]] += 1
    
MAX_h = max(counter_h.values())
h_list = [k for k, v in counter_h.items() if v == MAX_h]
MAX_w = max(counter_w.values())
w_list = [k for k, v in counter_w.items() if v == MAX_w]

import itertools

if len(h_list)*len(w_list)<=3*10**5:
    X = list(itertools.product(h_list, w_list))

    ans = MAX_h+MAX_w
    check = 0


    for i in range(M):
            if (h[i],w[i]) in X:
                check += 1

    if len(X)==check:
        ans -= 1
    
print(ans)

### FIXED CODE ###

H,W,M = map(int,input().split())
h = [0]*M
w = [0]*M

from collections import defaultdict
counter_h = defaultdict(int)
counter_w = defaultdict(int)

for i in range(M):
    h[i],w[i] = map(int, input().split())
    counter_h[h[i]] += 1
    counter_w[w[i]] += 1

MAX_h = max(counter_h.values())
h_list = [k for k, v in counter_h.items() if v == MAX_h]
MAX_w = max(counter_w.values())
w_list = [k for k, v in counter_w.items() if v == MAX_w]


ans = MAX_h+MAX_w
check = 0

for i in range(M):
    if counter_h[h[i]]==MAX_h and counter_w[w[i]]==MAX_w:
        check += 1

if len(h_list)*len(w_list)==check:
    ans -= 1

print(ans)
import math
def lcm(n,m): return n*m//math.gcd(n,m)
A,B,C,D=map(int,input().split())
print(((B-A)-(((B-A)//C)+((B-A)//D)))+((B-A)//lcm(C,D)))

### FIXED CODE ###

import fractions
a,b,c,d=map(int,input().split())
g=fractions.gcd(c,d)
l=c*d//g
print(b-b//c-b//d+b//l-(a-1-(a-1)//c-(a-1)//d+(a-1)//l))
A = [int(item) for item in input().split()]
N = A.pop(0)

print(' '.join([str(item) for item in A]))
for i in range(1, N):
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = key
    print(' '.join([str(item) for item in A]))

### FIXED CODE ###

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

print(' '.join([str(item) for item in A]))
for i in range(1, N):
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = key
    print(' '.join([str(item) for item in A]))
a,b,x=map(int,input().split())
x=0
for i in range(a):
    for j in range(b):
        if i==j:
            x += 1
print(x)

### FIXED CODE ###

a,b=map(int,input().split())
if a<=b:
    print(a)
else:
    print(a-1)
n = int(input())
m = int(input())
li = list(map(int,input().split()))
if n - sum(li) >= 0:
    print(n - sum(li))
else:
    print(-1)

### FIXED CODE ###

n,m = map(int,input().split())
li = list(map(int,input().split()))
if n - sum(li) >= 0:
    print(n - sum(li))
else:
    print(-1)
W, H, x, y = map(int,input().split())
hantei = 0
if (W%x == 0):
    if y*(W/x) == H:
        hantei = 1
print("{0} {1}".format(W*H/2, hantei))


### FIXED CODE ###

W, H, x, y = map(int,input().split())
hantei = 0
if (x != 0) and (y != 0):
    if (W/2 == x) and (H/2 == y):
        hantei = 1
print("{0} {1}".format(W*H/2, hantei))
S = include()
if S == 'S':
    print('Cloudy')
    elif S == "C":
        print('Rainy')
    elif S =='R':
        print('Sunny')
else
exit()

### FIXED CODE ###

import sys
S = input()
a = "Sunny"
b = 'Cloudy'
c = 'Rainy'
if S == a:
    print(b)
elif S == b:
        print(c)
elif S == c:
        print(a)
else:
    sys.exit()
sys.exit()
from fractions import Fraction

N = int(input())

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

from collections import defaultdict

arg = defaultdict(int)
zero = 0
for v in vec:
    if v[0] == 0 and v[1] == 0:
        zero += 1
    elif v[1]==0:
        arg[float("inf")] += 1
        arg[0] += 1
    else:
        arg[Fraction(v[0],v[1])] += 1
        arg[-1/Fraction(v[0],v[1])] += 0

pair = []

ll = lambda : False

checked_list = defaultdict(ll)

for key in arg:
    if not checked_list[key]:
        if key==0:
            pair.append([arg[0],arg[float("inf")]])
            checked_list[float("inf")] = True
        else:
            #print(key)
            pair.append([arg[key],arg[-1/key]])
            #print(pair)
            checked_list[-1/key] = True

mod = 1000000007

ans = 1

for p1,p2 in pair:
    ans *= pow(2,p1,mod) + pow(2,p2,mod) - 1
    ans %= mod

ans += zero
ans %= mod

print(ans-1)

### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(500000)

def gcd(a,b):
    a,b = max(a,b),min(a,b)
    while a%b!=0:
        a,b = b,a%b
    return b

def frac(a,b):
    d = gcd(abs(a),abs(b))
    if a<0:
        a = -a
        b = -b
    return (a//d,b//d)

def inv(a,b):
    return frac(-b,a)

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

def main():
    N = int(input())

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

    arg = defaultdict(int)
    zero = 0
    for v in vec:
        if v[0] == 0 and v[1] == 0:
            zero += 1
        elif v[1]==0:
            arg[float("inf")] += 1
            arg[0] += 0
        elif v[0]==0:
            arg[0] += 1
            arg[float("inf")] += 0
        else:
            arg[frac(v[0],v[1])] += 1
            arg[frac(-v[1],v[0])] += 0

    pair = []
    ll = lambda : False

    checked_list = defaultdict(ll)
    for key in arg:
        if not checked_list[key]:
            if key==0:
                pair.append([arg[0],arg[float("inf")]])
                checked_list[float("inf")] = True
            elif key==float("inf"):
                pair.append([arg[0],arg[float("inf")]])
                checked_list[0] = True

            else:
                #print(key)
                pair.append([arg[key],arg[inv(*key)]])
                #print(pair)
                checked_list[inv(*key)] = True

    mod = 1000000007

    ans = 1

    for p1,p2 in pair:
        ans *= pow(2,p1,mod) + pow(2,p2,mod) - 1
        ans %= mod

    ans += zero
    ans %= mod

    print((ans+mod-1)%mod)

if __name__ == '__main__':
    main()
A=map(int,input().split())
if A[0]=A[1]=A[2]:
    print("No")
elif　A[0]=A[1] orA[1]=A[2]:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

a,b,c=map(int,input().split())
if a==b==c:
    print("No")
elif a == b or b==c or c==a:
    print("Yes")
else:
    print("No")
A,B,C,K = map(int,input().split())
if K-A

A_num = A
B_num = 0
C_num = 0
if K>A:
  B_num = K-A
elif K-A>0:
  C_num = K-A-B

print(A_num*1+B_num*0+C_num*(-1))



### FIXED CODE ###

n = input()
a = input()
len_n = len(n)

if a[0:len_n]==n:
  print("Yes")
else:
  print("No")
def main():
    N, M = [int(n) for n in input().split()]
    from_li = [[] for i in range(N)] # from[i]:=点iからつながった点
    to_li = [[] for i in range(N)] # to[i]:=点iにつながる点
    for i in range(M):
        x, y = [int(n) for n in input().split()]
        from_li[x-1].append(y-1)
        to_li[y-1].append(x-1)
    parents = []
    children = []
    dp = [-1]*N
    for index, to in enumerate(to_li):
        if len(to) == 0:
            parents.append(index)
    for index, fr in enumerate(from_li):
        if(len(fr)) == 0:
            children.append(index)
    print(max([g(to_li, from_li, parents, dp, c) for c in children]))

    
def g(to_li, from_li, parents, dp, n):
    # nにつくパスの最大長
    if dp[n] != -1:
        return dp[n]
    if n in parents:
        return 0
    val = max([g(to_li, from_li, parents, dp, t)+1 for t in to_li[n]])
    dp[n] = val
    return val
    


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
def main():
    n, m = [int(n) for n in input().split()]
    paths = [[] for i in range(n+1)]
    for i in range(m):
        x, y = [int(r) for r in input().split()]
        paths[x].append(y)
    dp = [-1]*(n+1)

    ans = 0
    for i in range(n+1):
        ans = max(ans, dfs(paths, dp, i))
    print(ans-1)
def dfs(paths, dp, n):
    # nから下の最大長
    length = 0
    for p in paths[n]:
        val=0
        if dp[p] != -1:
            val = dp[p]
        else:
            val = dfs(paths, dp, p)
        length = max(length, val)
    length += 1 # pからnまでの一本もしくはnから終点までの一本
    dp[n] = length
    return length

if __name__ == "__main__":
    main()
import itertools as it
n,m=map(int,input().split())
path={[] for _ in range(m)}
for i in range(m): path[i]=list(map(int,input().split()))
ls=list(it.permutations(range(1,n+1)))
cnt=0
for l in ls:
    if l[0]==1: break
    for i in range(n-1):
        if [i,i+1] in path: cnt+=1
print(cnt)

### FIXED CODE ###

import itertools as it

n,m=map(int,input().split())
path=[]
for i in range(m): path.append(list(map(int,input().split())))
ls=list(it.permutations(range(1,n+1)))
cnt=0
for l in ls:
    if l[0]!=1: break
    flag=1
    for i in range(n-1):
        if ([l[i],l[i+1]] not in path) and ([l[i+1],l[i]] not in path):
            flag=0
            break
    if flag: cnt+=1
print(cnt)
import math
# N = int( input())

MOD = (10 ** 9) + 7
S = input()
dp = [ [ 0 for _ in range(4)]  for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S) ):
    if S[i] == "A":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += (dp[i][0] + dp[i][1])
        dp[i + 1][2] += (dp[i][2])
        dp[i + 1][3] += dp[i][3]
    if S[i] == "B":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] +=dp[i][1]
        dp[i + 1][2] +=  (dp[i][1] + dp[i][2])
        dp[i + 1][3] +=dp[i][3]

    if S[i] == "C":
        dp[i + 1][0] += (dp[i][0])
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += (dp[i][2] + dp[i][3])

    if S[i] == "?":
        dp[i + 1][0] +=  (dp[i][0] * 3)
        dp[i + 1][1] += (dp[i][0] + (dp[i][1]) * 3)
        dp[i + 1][2] += (dp[i][1]+ (dp[i][2]) * 3)
        dp[i + 1][3] += (dp[i][2]+ (dp[i][3]) * 3)
    for i in range(0,4):
        dp[i + 1][i] %= MOD




print(dp[-1][3] % MOD)

### FIXED CODE ###

import math
# N = int( input())

MOD = (10 ** 9) + 7
S = input()
dp = [ [ 0 for _ in range(4)]  for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S) ):
    if S[i] == "A":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += (dp[i][0] + dp[i][1])
        dp[i + 1][2] += (dp[i][2])
        dp[i + 1][3] += dp[i][3]
    if S[i] == "B":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] +=dp[i][1]
        dp[i + 1][2] +=  (dp[i][1] + dp[i][2])
        dp[i + 1][3] +=dp[i][3]

    if S[i] == "C":
        dp[i + 1][0] += (dp[i][0])
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += (dp[i][2] + dp[i][3])

    if S[i] == "?":
        dp[i + 1][0] +=  (dp[i][0] * 3)
        dp[i + 1][1] += (dp[i][0] + (dp[i][1]) * 3)
        dp[i + 1][2] += (dp[i][1]+ (dp[i][2]) * 3)
        dp[i + 1][3] += (dp[i][2]+ (dp[i][3]) * 3)
    for j in range(0,4):
        dp[i + 1][j] %= MOD




print(dp[-1][3] % MOD)
N, D = map(int, input().split())

result = N // (2D+1) + 1

print(result)

### FIXED CODE ###

N, D = map(int, input().split())
 
result = -(-N // (2*D+1))
 
print(result)
a = input()

if(s.islower):
    print("a")
else:
    print("A")


### FIXED CODE ###

s = input()

if(s.islower()):
    print("a")
elif(s.isupper()):
    print("A")
Q = int(input())


M = 10**5 + 5
primes = [True] * M
primes[0] = False
primes[1] = False


for i in range(2, M):
    if primes[i]:
        for j in range(2, M//i):
            primes[i*j] = False

cnt = [0] * M

for i in range(3, M):
    cnt[i] = cnt[i-1]
    if primes[i] and primes[(i+1)//2]:
        cnt[i] += 1

for q in range(Q):
    l, r = map(int, input().split())
    print(cnt[r] - cnt[l-1])


### FIXED CODE ###

print(48-int(input()))
N = int(input())
P = list(map(int, input().split()))

count = 1
if P[1] <= P[0]:
  count+=1
for i in range(2,N):
  if P[i] <= min(P[:i-1]):
    count+=1
print(count)


### FIXED CODE ###

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

count = 1
if N == 1:
  print(count)
else:
  min = P[0]
  if P[1] <= P[0]:
    count+=1
    min = P[1]

  for i in range(2,N):
    if P[i] <= min:
      count+=1
      min = P[i]
  print(count)