Harryxun/stf_run huggingface dataset:
import sys

N, M = map(int,input().split())
es = []
for _ in range(M):
    e = list(map(int,input().split()))
    e[2] *= -1
    es.append(e)

INF = float('inf')
d = [INF for _ in range(N+1)]
d[1] = 0
negative = [0 for _ in range(N+1)]
for i in range(N):
    for j in range(M):
        e = es[j]
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            if i == N-1:
                negative[e[0]] = 1
                negative[e[1]] = 1
for i in range(M):
    e = es[i]
    if negative[es[0]] or negative[es[1]]:
        negative[es[0]] = 1
        negative[es[1]] = 1
if negative[N]:
    print('inf')
else:
    print(d[N])

### FIXED CODE ###

import sys

N, M = map(int,input().split())
es = []
for _ in range(M):
    e = list(map(int,input().split()))
    e[2] *= -1
    es.append(e)

INF = float('inf')
d = [INF for _ in range(N+1)]
d[1] = 0
negative = [0 for _ in range(N+1)]
for i in range(N):
    for j in range(M):
        e = es[j]
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            if i == N-1:
                negative[e[0]] = 1
                negative[e[1]] = 1
for i in range(M):
    e = es[i]
    if negative[e[0]]:
        negative[e[1]] = 1
if negative[N]:
    print('inf')
else:
    print(-d[N])
N = int(input())
A = list(map(int, input().split()))

money = 1000
ticket = 0
for i in range(N):
    # buy
    if A[i] < A[i + 1]:
        money -= (money // A[i]) * A[i]
        ticket += money // A[i]
    elif A[i] == A[i + 1]:
        pass
    # sell
    else:
        money += A[i] * ticket
        ticket = 0


### FIXED CODE ###

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

money = 1000
ticket = 0
for i in range(N - 1):
    # buy
    if A[i] < A[i + 1]:
        ticket += money // A[i]
        money -= (money // A[i]) * A[i]
    elif A[i] == A[i + 1]:
        pass
    # sell
    else:
        money += A[i] * ticket
        ticket = 0

money += A[-1] * ticket

print(money)
N=int(input())
xyh=[list(map(int,input().split())) for i in range(N)]
from itertools import product
H={(i,j):-10**9 for i,j in product(range(101),repeat=2)}
for n in range(N):
    x,y,h=xyh[n]
    K=[e for e in H.keys()]
    for i,j in K:
        k0=H[i,j]
        k=abs(i-x)+abs(j-y)+h if h else -(abs(i-x)+abs(j-y))
        if k<0:
            if k0<k:
                H[i,j]=k
            elif -k<k0:
                del H[i,j]
        elif k0<0:
            if k<=-k0:
                H[i,j]=k
            else:
                del H[i,j]
        elif k!=k0:
            del H[i,j]
i,j=list(H.keys())[0]
print(i,j,H[i,j])

### FIXED CODE ###

N=int(input())
xyh=[list(map(int,input().split())) for i in range(N)]
from itertools import product
H={(i,j):-10**10 for i,j in product(range(101),repeat=2)}
for n in range(N):
    x,y,h=xyh[n]
    K=[e for e in H.keys()]
    for i,j in K:
        k0=H[i,j]
        k=abs(i-x)+abs(j-y)+h if h else -(abs(i-x)+abs(j-y))
        if k<0:
            if k0<k:
                H[i,j]=k
            elif -k<k0:
                del H[i,j]
        elif k0<0:
            if k<=-k0:
                H[i,j]=k
            else:
                del H[i,j]
        elif k!=k0:
            del H[i,j]
i,j=list(H.keys())[0]
print(i,j,H[i,j])
K = int(input())
S = input()

length = len(s)
if K >= length:
    print(S)
else:
    print(S[:K] + '...')


### FIXED CODE ###

K = int(input())
S = input()

if K >= len(S):
    print(S)
else:
    print(S[:K] + '...')
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
a,b = map(int, input().split()) 

if b==0:
    print(a)
    exit()
num_list = list(map(int, input().split()))

    

num=[True]*101
#print(num)


for i in range(b):
    num[num_list[i]]=False


num[0]=False
#print(num)

count=0
min_min=100
min_max=100
i=a

#print(i)
while 1:
    if i==100:
        break
    if num[i]==True:
        min_min=i-a
        break
    i+=1
j=a


while 1:
    if num[j]==True:
        min_max=a-j
        break
    j-=1
#print(min_max)
#print(j)
if min_min<min_max:
    print(i)
    
else:
    print(j)


### FIXED CODE ###

x,y=map(int,input().strip().split())
nums = list(map(int, input().strip().split()))
ans=0
if y==0:
  print(x)
elif x not in nums:
  print(x)
else:
  for i in range(0,102):
    if i not in nums:
      if abs(x-i)<abs(x-ans):
        ans=i
  print(ans)
# -*- coding:utf-8 -*-

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    As.sort()

    setA = set(As)
    setDel = set()

    cands = []

    for a in As:
        if a in setDel:
            continue

        i = 1
        while a*i <= As[-1]:
            if a*i in setA:
                setDel.add(a*i)
            i += 1

        cands.append(a)

    # 重複する数字を調べる
    dic = {}
    for a in As:
        if not a in dic:
            dic[a] = 0
        elif dic[a] == 1:
            cands.remove(a)
        dic[a] += 1

    print(len(cands))


if __name__ == "__main__":
    solve()


### FIXED CODE ###

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

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    As.sort()

    setA = set(As)
    setDel = set()

    cands = []

    for a in As:
        if a in setDel:
            continue

        i = 1
        while a*i <= As[-1]:
            if a*i in setA:
                setDel.add(a*i)
            i += 1

        cands.append(a)

    # 重複する数字を調べる
    dic = {}
    for a in As:
        if not a in dic:
            dic[a] = 0
        dic[a] += 1

    ans = 0
    for x in cands:
        if dic[x] > 1:
            continue
        ans += 1

    print(ans)


if __name__ == "__main__":
    solve()
n = int(input())
*A, = map(int, input().split())
DP = [[None for j in range(n+1)] for i in range(n)]
def dp(i, j):
    if i == j:
        return 0
    if DP[i][j] != None:
        return DP[i][j]
    DP[i][j] = max(A[i]-dp(i+1, j), A[j-1]-dp(i, j-1))
    return DP[i][j]
print(dp(0, n))


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for l in range(1, n+1):
    for i in range(n-l+1):
        DP[i][i+l] = max(A[i]-DP[i+1][i+l], A[i+l-1]-DP[i][i+l-1])
print(DP[0][n])
li= list(map(int, input().split()))
li.insert(1, li.pop(0))
li.insert(2, li.pop(0))
li.insert(0, li.pop(1))
print(li(0), li(1), li(2))


### FIXED CODE ###

li= list(map(int, input().split()))
li.insert(1, li.pop(0))
li.insert(2, li.pop(0))
li.insert(0, li.pop(1))
print(li[0], li[1], li[2])
a,b,c=sorted(map(int,input().split()))
print('Yes' if x+y==z else 'No')


### FIXED CODE ###

a,b,c=sorted(map(int,input().split()))
print('Yes' if a+b==c else 'No')
A = 0
S = input()
fot n in range(1,int(S)+1):
 A = A + n
print(A)

### FIXED CODE ###

A = 0
S = input()
for n in range(1,int(S)+1):
 A = A + n
print(A)
n = int(input())
a_li = list(map(int, input().strip().split()))

a_set = set(a_li)

for i in range(1, n+1):
  if i in a_set:
    print(a_li.count(i))
    else:
      print(0)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a_li = list(map(int, input().strip().split()))

    a_dict = {}

    for a in a_li:
        if str(a) in a_dict:
            a_dict[str(a)] += 1
        else:
            a_dict[str(a)] = 1

    for i in range(1, n+1):
        if str(i) in a_dict:
            print(a_dict[str(i)])
        else:
            print(0)

if __name__ == '__main__':
    main()
def main(A: int, B: int, C: int, D: int):
    train, bus = 0, 0
    if A <= B:
        train += A
    else:
        train += B

    if C <= D:
        bus += C
    else:
        bus += D

    return train + bus


if __name__ == '__main__':
    A, B, C, D = map(int, input().split(' '))
    print(main(A, B, C, D))


### FIXED CODE ###

def main(A: int, B: int, C: int, D: int):
    train, bus = 0, 0
    if A <= B:
        train += A
    else:
        train += B

    if C <= D:
        bus += C
    else:
        bus += D

    return train + bus


if __name__ == '__main__':
    A = int(input())
    B = int(input())
    C = int(input())
    D = int(input())
    print(main(A, B, C, D))
n =int(input())
a =[int(input()) for i in range(n)]

dict = {}
for i in range(n):
  if not(a[i] in dict):
    dict(a[i]) ==1
  if s[i] in dict:
    dict.pop(a[i])
    
print(len(dict))
  

### FIXED CODE ###

n = int(input())
d = {}
for i in range(n):
    a = int(input())
    if a in d:
        del d[a]
    else:
        d[a] = 1
print(len(d))
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://qiita.com/drken/items/97e37dd6143e33a64c8c#3-%E3%82%81%E3%81%90%E3%82%8B%E5%BC%8F%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E3%81%AE%E3%81%95%E3%82%89%E3%81%AA%E3%82%8B%E5%88%A9%E7%82%B9

    n,a,b=map(int,input().split())
    h=[int(input()) for _ in range(n)]
    def is_ok(t):
        cnt=0
        for i in range(n):
            val=math.ceil((h[i]-b*t) / (a-b))
            cnt+=val
        if cnt<=t:
            return True
        else: return False

    def bin_search_meguru():
        """
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng, okは,とり得る最小の値-1,とり得る最大の値+1
        """
    
        # 適当にいじる
        ng = 0  # ind=0が条件を満たすこともあるため
        ok = 10**9+1  # ind=len(a)-1が条件を満たさないこともあるため
    
        # いじらない
        # okとngのどちらが大きいかわからないことを考慮
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    print(bin_search_meguru())
    

    
resolve()

### FIXED CODE ###

import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://qiita.com/drken/items/97e37dd6143e33a64c8c#3-%E3%82%81%E3%81%90%E3%82%8B%E5%BC%8F%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E3%81%AE%E3%81%95%E3%82%89%E3%81%AA%E3%82%8B%E5%88%A9%E7%82%B9

    n,a,b=map(int,input().split())
    h=[int(input()) for _ in range(n)]
    def is_ok(t):
        cnt=0
        for i in h:
            i-=b*t
            if i>0:
                cnt+=math.ceil(i / (a-b))
        return cnt<=t

    def bin_search_meguru():
        """
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng, okは,とり得る最小の値-1,とり得る最大の値+1
        """
    
        # 適当にいじる
        ng = 0  # ind=0が条件を満たすこともあるため
        ok = 10**18  # ind=len(a)-1が条件を満たさないこともあるため
    
        # いじらない
        # okとngのどちらが大きいかわからないことを考慮
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    print(bin_search_meguru())
    

    
resolve()
n = input()
str = input()
sl = list(str.split(" ")[0])
tl = list(str.split(" ")[1])

for i in range(0,n-1):
    print(sl[i],end="")
    print(tl[i],end="")



### FIXED CODE ###

n = input()
str = input()
sl = list(str.split(" ")[0])
tl = list(str.split(" ")[1])

for i in range(0,int(n)):
    print(sl[i],end="")
    print(tl[i],end="")
result = 0

N, K=map(int,input().strip().split(' '))

if N mod K != 0:
  result = 1

print(result)

### FIXED CODE ###

result = 0

N, K=map(int,input().strip().split(' '))

if N % K != 0:
  result = 1

print(result)
largenum = 10**18
def main():
    n = int(input())
    a = list(map(int, input().split()))

    r = a[0]
    for i1 in range(1, n):
        if r > largenum:
            print(-1)
            sys.exit()
        else:
            r *= a[i1]
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
largenum = 10**18
from functools import reduce
from operator import mul
def main():
    n = int(input())
    a = list(map(int, input().split()))

    if 0 in a:
        print(0)
        sys.exit()
    r = 1
    for i1 in range(n):
        r *= a[i1]
        if r > largenum:
            print(-1)
            sys.exit()
    print(r)


if __name__ == '__main__':
    main()
D=int(input())
c=list(map(int,(input().split())))
s=[]
t=[]
last=[0]*26
sat=0
for _ in range(D):
  s.append(list(map(int,(input().split()))))


for i in range(D):
  sat+=max(s[i])
  t.append(s[i].index(max(s[i]))+1)
  for j in range(26):
    sat-=c[i]*(1-last[j])
  
for ans in t:
  print(ans)

### FIXED CODE ###

D=int(input())
c=list(map(int,(input().split())))
s=[]
t=[]
last=[0]*26
sat=0
  
for i in range(D):
  s.append(list(map(int,(input().split()))))
  sat+=max(s[i])
  ans=s[i].index(max(s[i]))+1
  t.append(ans)
  print(ans)
n, m = list(map(int, input().split()))

# initialize the cards array. True means the card shows back side
arr = [ [False] * m ] * n

for i in range(n):
    for j in range(m):
        for a in [-1, 0, 1]:
            for b in [-1, 0, 1]:
                if i-b >=0 and j-a >= 0:
                    try:
                        arr[i-b][j-a] = not arr[i-b][j-a]
                    except IndexError:
                        pass
        print(i,j, arr)

print(sum(sum(l) for l in arr))

### FIXED CODE ###

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

if n == 1 and m == 1:
    print(1)
elif n == 1 and m > 1:
    print(m - 2)
elif n > 1 and m == 1:
    print(n - 2)
else:
    print((n-2)*(m-2))
from decimal import *
num1, num2, num3 = map(int, input().split())
num1 = Decimal(num1)
num2 = Decimal(num2)
num3 = Decimal(num3)
if (num.sqrt() + num2.sqrt() < num3.sqrt()):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

from decimal import *
num1, num2, num3 = map(int, input().split())
num1 = Decimal(num1)
num2 = Decimal(num2)
num3 = Decimal(num3)
if (num1.sqrt() + num2.sqrt() < num3.sqrt()):
  print("Yes")
else:
  print("No")
import sys
from collections import defaultdict
dic1 = defaultdict(int)
dic2 = defaultdict(int)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7
def pow(n,p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return (a//gcd(a,b)*b)
def to_standard_form(a, b):
    if a == 0:
        return (0, 1)
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        return (-a, -b)
    return (a, b)
n = int(readline())
zero = 0
for i in range(n):
    a,b= map(int,readline().split())
    if a == b == 0:
        zero += 1
        continue
    plamai = 1 if a*b > 0 else 0
    a,b = to_standard_form(a,b)
    if b <= 0:
        dic2[(a,b)] += 1
    else:
        dic1[(b,-a)] += 1
        dic2[(b,-a)] += 0

ans = zero
k = 1
for key,cnt in dic2.items():
    cnt2 = dic1[key]
    k = pow(2,cnt)+pow(2,cnt2)
    k = k*(x-1)%mod
print((ans+k-1)%mod)

### FIXED CODE ###

import sys
from collections import defaultdict
dic1 = defaultdict(int)
dic2 = defaultdict(int)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7
def pow(n,p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return (a//gcd(a,b)*b)
def to_standard_form(a, b):
    if a == 0:
        return (0, 1)
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        return (-a, -b)
    return (a, b)
n = int(readline())
zero = 0
for i in range(n):
    a,b= map(int,readline().split())
    if a == b == 0:
        zero += 1
        continue
    plamai = 1 if a*b > 0 else 0
    a,b = to_standard_form(a,b)
    if b <= 0:
        dic2[(a,b)] += 1
    else:
        dic1[(b,-a)] += 1
        dic2[(b,-a)] += 0

ans = zero
k = 1
for key,cnt in dic2.items():
    cnt2 = dic1[key]
    x = pow(2,cnt)+pow(2,cnt2)
    k = k*(x-1)%mod
print((ans+k-1)%mod)
import math
N = [float(e) for e in input().split()]
ans = str(N[0]*N[1])
ans1 = ans[0:-2]
print(int(ans1))

### FIXED CODE ###

from decimal import Decimal
N = [Decimal(e) for e in input().split()]
ans = Decimal(N[0]) * Decimal(N[1])
print(int(ans))
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
s = 0
for i in range(n):
  s += b[a[i]]
  if i < n-1 and a[i+1] == a[i]+1:
    s += c[i]

print(s)



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
s = 0
for i in range(n):
  s += b[a[i]-1]
  if 0 < i  and a[i] == a[i-1]+1:
    s += c[a[i-1]-1]

print(s)
x, n  = map(int, input().split())
p = map(int, intput().split())

m = -1
for a in p:
  if m == -1 or (abs(a - x) < abs(m - x)) or (abs(a - x) == abs(m - x) and a < m):
    m = a

print(m)

### FIXED CODE ###

x, n  = map(int, input().split())
if n > 0:
  p = set(map(int, input().split()))
  i = 0
  while True:
    if x - i not in p:
      print(x-i)
      break
    if x + i not in p:
      print(x+i)
      break
    i += 1
else:
  print(x)
A, B, C, D = map(int, input().split())
import math
ccount = ((B//C*C)-((A-1)//C*C +C))/C +1
dcount = ((B//D*D)-((A-1)//D*D +D))/D +1
lcm = (C * D) // math.gcd(C, D)
cdcount = ((B//lcm*lcm)-((A-1)//lcm*lcm +lcm))/lcm +1
count = B-A+1-ccount - dcount +cdcount
print(int(count))

### FIXED CODE ###

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

import fractions
ccount = ((B//C*C)-((A-1)//C*C +C))//C +1
dcount = ((B//D*D)-((A-1)//D*D +D))//D +1
lcm = (C * D) // fractions.gcd(C, D)
cdcount = ((B//lcm*lcm)-((A-1)//lcm*lcm +lcm))//lcm +1
count = B - A + 1 - ccount - dcount + cdcount
print(int(count))
A, B, X = map(int, inpput().split())
print("YES" if A <= X and A+B >= X else "NO")


### FIXED CODE ###

A, B, X = map(int, input().split())
print("YES" if A <= X and A+B >= X else "NO")
x = input().split()
n = 0
for i in range(1,int(x[0])+1):
    l = 0
    for j in range(1,i+1):
               if x[i] <= x[j]:
                    l += 1
    if l == i:
        n += 1
print(n)

### FIXED CODE ###

x = input().split()
if x[0] == x[1]:
    print("Yes")
else :
    print("No")
# -*- coding: utf-8 -*-

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
"""

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

# あるBの位置よりも左にあるAと?の個数
A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq
# あるBの位置よりも右にあるCと?の個数
C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # (A,B,C) と選ぶ場合(後ろの3**LQ[i] * 3**RQ[i]は使わなかった?の分)
        case1 = A[i] * C[i] * pow(3, LQ[i]) * pow(3, RQ[i])
        # (A,B,?) と選ぶ場合
        case2 = A[i] * RQ[i] * pow(3, LQ[i]) * pow(3, RQ[i]-1)
        # (?,B,C) と選ぶ場合
        case3 = LQ[i] * C[i] * pow(3, LQ[i]-1) * pow(3, RQ[i])
        # (?,B,?) と選ぶ場合
        case4 = LQ[i] * RQ[i] * pow(3, LQ[i]-1) * pow(3, RQ[i]-1)
        # 全部足し合わせてMOD
        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,b,n = map(int,input().split())
n%b==0:n-=1
print((a*n)//b-a*(n//b))

### FIXED CODE ###

a,b,n = map(int,input().split())
if n%b==0:n-=1
x = max((n//b)*b-1,n%b)
print(((a*x)//b)-(a*(x//b)))
import numpy as np
# 参加人数を入力する
N = int(input())
# レートを入力する
a = list(map(int, input().split()))
# ndarray型に変換
arr_a = np.array(a)
# 3200未満のレートを持つ人について、色の種類数を設定する
under3200 = 0
# 色ごとのレートの下限と上限を設定
lower = 1
upper = 399
# 上限が3200未満である限り繰り返す
while upper < 3200:
    # 範囲内のレートを持つ人がいる場合、色の種類数を増やす
    if len(arr_a[(arr_a  >= lower) & (arr_a <= upper)]) != 0:
        under3200 += 1
    # 下限と上限を更新する
    lower = upper + 1
    upper += 400
# 3200を超えるレートを持つ人の数を数える
over3200 = len(arr_a[arr_a >= 3200])
# 規定の色の数を設定する
color = 8

# 色の種類数の最小値について
if over3200 <= under3200:
    min_color = under3200
elif over3200 < color:
    min_color = overcolor
else:
    min_color = 8
# 色の種類数の最大値について
if under3200 + over3200 < color:
    max_color = under3200 + over3200
else:
    max_color = color
# 結果を出力する
print("{} {}".format(min_color, max_color))

### FIXED CODE ###

import numpy as np
# 参加人数を入力する
N = int(input())
# レートを入力する
a = list(map(int, input().split()))
# ndarray型に変換
arr_a = np.array(a)
# 3200未満のレートを持つ人について、色の種類数を設定する
under3200 = 0
# 色ごとのレートの下限と上限を設定
lower = 1
upper = 399
# 上限が3200未満である限り繰り返す
while upper < 3200:
    # 範囲内のレートを持つ人がいる場合、色の種類数を増やす
    if len(arr_a[(arr_a  >= lower) & (arr_a <= upper)]) != 0:
        under3200 += 1
    # 下限と上限を更新する
    lower = upper + 1
    upper += 400
# 3200を超えるレートを持つ人の数を数える
over3200 = len(arr_a[arr_a >= 3200])

# 色の種類数の最小値について
if under3200 != 0:
    min_color = under3200
else:
    min_color = 1
# 色の種類数の最大値について
max_color = under3200 + over3200
# 結果を出力する
print("{} {}".format(min_color, max_color))
a,b = list(map(int, input().split()))
print(a*b, 2(a+b))

### FIXED CODE ###

a,b = list(map(int, input().split()))
print(a*b, 2*(a+b))
N,Q=map(int,input().split())
S=input()
count=[0]*(N)
for i in range(N-1):
    if S[i:i+2]=="AC":
        count[i]=1
sums=list(accumulate([0]+count))

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


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
l=[]
r=[]
lst1=[0 for i in range(N)]
for i in range(N-1):
    i+=1
    if S[i-1:i+1]=="AC":
        lst1[i]=lst1[i-1]+1
    else:
        lst1[i]=lst1[i-1]

for i in range(Q):
    l,r=map(int,input().split())
    l=l-1
    r-=1
    print(lst1[r]-lst1[l])
from collections import defaultdict

N, K = map(int, input().split())
A = list(map(int, input().split()))
cum = [0]*(N+1)
for i in range(1,N+1):
    cum[i] = cum[i-1] + A[i-1]
ans = 0
dic = defaultdict(int)
v_by_indx = defaultdict(int)
for i in range(N+1):
    if i-K >= 0:
        dic[v_by_indx[i-K]] -= 1
    diff = (cum[i]-i)%K
    ans += dic[diff]
    dic[diff] += 1
    v_by_indx[i] = diff
print(ans)
from collections import defaultdict

N, K = map(int, input().split())
A = list(map(int, input().split()))
cum = [0]*(N+1)
for i in range(1,N+1):
    cum[i] = cum[i-1] + A[i-1]
ans = 0
dic = defaultdict(int)
v_by_indx = defaultdict(int)
for i in range(N+1):
    if i-K >= 0:
        dic[v_by_indx[i-K]] -= 1
    diff = (cum[i]-i)%K
    ans += dic[diff]
    dic[diff] += 1
    v_by_indx[i] = diff
print(ans)

### FIXED CODE ###

from collections import defaultdict

N, K = map(int, input().split())
A = list(map(int, input().split()))
cum = [0]*(N+1)
for i in range(1,N+1):
    cum[i] = cum[i-1] + A[i-1]
ans = 0
dic = defaultdict(int)
v_by_indx = defaultdict(int)
for i in range(N+1):
    if i-K >= 0:
        dic[v_by_indx[i-K]] -= 1
    diff = (cum[i]-i)%K
    ans += dic[diff]
    dic[diff] += 1
    v_by_indx[i] = diff
print(ans)
import math
n=list(map(int,input().split(' ')))
ans=(n[0]*n[1])//math.gcd(n[0],n[1])
print(ans)

### FIXED CODE ###

n=list(map(int,input().split(' ')))
import fractions
ans=(n[0]*n[1]) // fractions.gcd(n[0],n[1])
print(ans)