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

import numpy as np
from scipy.sparse.csgraph import dijkstra

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
shortcut = dijkstra(A, directed=False)
if not np.array_equal(A, shortcut):
    print(-1)
    exit()

for i in range(N):
    for j in range(i+1,N):
        if A[i, j] == 0:
            continue
        for k in range(N):
            if A[i, k] == 0 or A[j, k] == 0:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                A[i, j] = A[j, i] = 0

print(sum(sum(A))//2)

### FIXED CODE ###

def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')


def main():
    H, W, K = map(int, readline().split())
    # いつものパターンと問題文のi,jが逆なので、
    # 問題文のxを変数yに、問題文のyを変数xに代入している
    sy, sx, gy, gx = map(int, readline().split())
    sy -= 1
    sx -= 1
    gx -= 1
    gy -=1
    lake = read().split()
    dist = [[INF] * W for _ in range(H)]
    dxy = ((1, 0), (0, 1), (-1, 0), (0, -1))
    Q = deque()
    Q.append((sy, sx, 0))
    dist[sy][sx] = 0
    while Q:
        y,x,d = Q.popleft()
        if (y,x) == (gy, gx):
            print(d)
            sys.exit()
        for dx,dy in dxy:
            n_y = y
            n_x = x
            for _ in range(K):
                n_y +=dy
                n_x +=dx

                if 0<=n_x<W and 0<=n_y<H and lake[n_y][n_x] != '@':
                    if dist[n_y][n_x]<d:
                        break
                    elif dist[n_y][n_x] == INF:
                        dist[n_y][n_x] = d + 1
                        Q.append((n_y,n_x,d+1))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())

uf = UnionFind(N)

for i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

all_group_members = uf.all_group_members()
ans = 0

for r in uf.roots():
    ans = max(ans, len(uf.members(r)))

print(ans)




### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())

uf = UnionFind(N)
# check = set()

for i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    # check.add(a-1)

# ans = 0
# for i in check:
#     ans = max(ans, uf.size(i))

print(min(uf.parents)*(-1))

# print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
a = "SS"
ct=1
while ct<7:    
    for i in range(n-1):
        p=a[i]
        q="A"
        if a[i]=="S":
            q="W"
        else:
            q="S"
        if a[i+1]=="S":
            if s[i+1] == "o":
                a=a+a[i]
            else:
                a=a+q
        else:
            if s[i+1] == "o":
                 a=a+q
            else:
                a=a+a[i]
    if a[0]==a[n]:
        if a[0]=="S":
            if s[0]=="o":
                if a[n-1]==a[1]:
                    print(a[0:n])
                    break
                else:
                    pass
            else:
                if a[n-1]==a[1]:
                    pass
                else:
                    print(a[0:n])
                    break
        else:
            if s[0]=="o":
                if a[n-1]==a[1]:
                    pass
                else:
                    print(a[0:n])
                    break
            else:
                if a[n-1]==a[1]:
                    print(a[0:n])
                    break
                else:
                    pass
    else:
        ct=ct+1
        if ct==2:
            a="SW"
        elif ct==3:
            a="WS"
        elif ct==4:
            a="WW"
        else:
            print(-1)
            break

### FIXED CODE ###

n = int(input())
s = input()
a = "SS"
ct=1
while ct<7:    
    for i in range(n-1):
        p=a[i]
        q="A"
        if a[i]=="S":
            q="W"
        else:
            q="S"
        if a[i+1]=="S":
            if s[i+1] == "o":
                a=a+a[i]
            else:
                a=a+q
        else:
            if s[i+1] == "o":
                 a=a+q
            else:
                a=a+a[i]
    if a[0]==a[n]:
        if a[0]=="S" and s[0]=="o" and a[n-1]==a[1]:
            print(a[0:n])
            break
        elif a[0]=="S" and s[0] !="o" and a[n-1]!=a[1]:         
            print(a[0:n])
            break
        elif a[0]=="W" and s[0] =="o" and a[n-1]!=a[1]: 
            print(a[0:n])
            break
        elif a[0]=="W" and s[0] !="o" and a[n-1]==a[1]: 
            print(a[0:n])
            break
        else:
            ct=ct+1
        if ct==2:
            a="SW"
        elif ct==3:
            a="WS"
        elif ct==4:
            a="WW"
        else:
            print(-1)
            break
    else:
        ct=ct+1
        if ct==2:
            a="SW"
        elif ct==3:
            a="WS"
        elif ct==4:
            a="WW"
        else:
            print(-1)
            break
### BUGGY CODE ###

from collections import deque
N = int(input())
uvw = [[]for i in range(N)]
for i in range(N-1):
    u,v,w = list(map(int,input().split()))
    uvw[u-1].append([v-1,w%2])
    uvw[v-1].append([u-1,w%2])    
color = [0 for i in range(N)]
que = deque()
que.append(0)
alr = [0]
while que:
    q = que.popleft()
    colorq = color[q]
    for i in uvw[q]:
        if i[0] not in alr:
            que.append(i[0])
            alr.append(i[0])
            if i[1] == 0:
                color[i[0]] = colorq
            else:
                color[i[0]] = abs(colorq-1)
for i in color:
    print(i)

### FIXED CODE ###

from collections import deque
N = int(input())
uvw = [[]for i in range(N)]
for i in range(N-1):
    u,v,w = list(map(int,input().split()))
    uvw[u-1].append([v-1,w%2])
    uvw[v-1].append([u-1,w%2])    
color = [-1 for i in range(N)]
color[0] = 0
que = deque()
que.append(0)
while que:
    q = que.popleft()
    colorq = color[q]
    for i in uvw[q]:
        if color[i[0]] == -1:
            que.append(i[0])
            if i[1] == 0:
                color[i[0]] = colorq
            else:
                color[i[0]] = abs(colorq-1)
for i in color:
    print(i)
### BUGGY CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z==s:
        cnt+=1
        
print(cnt)

### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
  for y in range(k+1):
    z=s-x-y
    if z>=0 and z<=k:
      cnt+=1
        
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)


f=0
for i in a:
    if i+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
  

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)


f=0
for i in range(al-1):
    if a[i+1]==a[i]+1:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
### BUGGY CODE ###

n = int(input())

count = 0
for c in range(1,n+1):
  for a in range(1,n-c+1):
    if (n-c)%a == 0:
      count += 1
      #print(a,(n-c)//a,c)
print(count)

### FIXED CODE ###

n = int(input())

count = 0
for a in range(1,n):
  count += (n-1)//a

print(count)
### BUGGY CODE ###

import sys
from math import log2,floor
stdin = sys.stdin
N = int(stdin.readline().rstrip())
A = list(map(int,stdin.readline().split()))
mod = 10**9+7
ans = 0
for i in range(61):
    bits = 0
    for x in A:
        if (x>>i)&1:
            bits += 1
    ans += ((bits*(N-bits))* 2**i) %mod
ans %= mod
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
mod = 10**9 + 7
 
def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))
 
def main():
    n = ni()
    a = na()
    ans = 0
    for i in range(61):
        cnt = 0
        for ai in a:
            if (ai >> i) & 1:
                cnt += 1
        ans += ((cnt * (n - cnt)) * 2**i) % mod
    ans %= mod
    print(ans)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

R, G, B ,N = list(map(int, input().split(' ')))

cnt = 0

_R = N//R
_G = N//G
_B = N//B

for i in range(_R+1):
    for j in range(_G+1):
        if  i*R + j*G > N:
            break
        for k in range(_B+1):
            if i*R + j*G + k*B == N:
                cnt += 1
            elif i*R + j*G + k*B > N:
                break
print(cnt)

### FIXED CODE ###

R, G, B ,N = list(map(int, input().split(' ')))

cnt = 0

li = [R, G, B]
li = sorted(li)

_i = N//li[2]
for i in range(_i+1):
    _j = (N - li[2]*i )//li[1]
    for j in range(_j + 1):
        if (N - i*li[2] -  j*li[1])%li[0] == 0:
            cnt += 1

print(cnt)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range(N//R+1):
	for g in range(N//G+1):
		if (N-R*r-G*g)%B==0 and (N-R*r-G*g)//B>=0:
			cnt += 1

print(cnt)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range(N//R+1):
	n=N-r*R
	for g in range(n//G+1):
		n1=n-G*g
		if n1%B==0 and n1//B>=0:
			cnt += 1

print(cnt)
### BUGGY CODE ###

S = list(input())
Quve = []
count = 0
flag = 0
for i in range(len(S)):
    if int(S[i])==0:
        Quve.append("a")#赤文字をaで表記
    else:
        Quve.append("b")
Quve.append("")
while(flag ==0):
    tmp = count
    for i in range(len(Quve)-1):
        if ((Quve[i]=="a") & (Quve[i+1]=="b")) | ((Quve[i]=="b") & (Quve[i+1]=="a")):
            del Quve[i]
            del Quve[i]
            count += 2
            break
    if (tmp == count):
        flag = 1
print(count)


### FIXED CODE ###

#TLE
# 0と1を数えて少ないほうの2倍を取れば勝ち
S = list(input())
count0 = 0
count1 = 0
for i in range(len(S)):
    if S[i]=='0':
        count0 += 1
    else:
        count1 += 1
print(2*min(count0,count1))
### BUGGY CODE ###

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

d = deque(['S'])

#d = ['S']

rev = 0

for i in range(q):
    if query[i][0] == '2':
        if query[i][1] == '1':
            d.appendleft(query[i][2])
        else:
            d.append(query[i][2])
    else:
        d.reverse()
        rev += 1

ans = deque()

if rev % 2 == 1:
    s = ''.join(list(reversed(s)))
"""
while len(d):
    tmp = d.popleft()
    if tmp == 'S':
        ans.append(s)
    else:
        ans.append(tmp)
"""
d = [s if i == 'S' else i for i in d]

print(*d,sep='')


### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

d = deque(['S'])

#d = ['S']

rev = False

for i in range(q):
    if query[i][0] == '1':
        rev = not rev
        continue
    
    if not rev:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.appendleft(query[i][2])
            else:
                d.append(query[i][2])
    else:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.append(query[i][2])
            else:
                d.appendleft(query[i][2])

#ans = deque()
if rev:
    #d = ''.join(list(reversed(d)))
    s = s[::-1]



while len(d):
    if rev:
        tmp = d.pop()
    else:
        tmp = d.popleft()
    if tmp == 'S':
        #ans.append(s)
        print(s,end='')
    else:
        print(tmp,end='')
        #ans.append(tmp)

#print(*ans,sep='')
### BUGGY CODE ###

n, q = map(int, input().split())
ab = [[] for _ in range(n)]
px = [0 for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ab[a - 1].append(b - 1)
    ab[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    px[p - 1] += x

ans = px
queue = [(0, 0)]

while len(queue) > 0:
    prev, a = queue.pop(0)
    for c in ab[a]:
        if c != prev:
            ans[c] += ans[a]
            queue.append((a, c))

print(*ans)


### FIXED CODE ###

from collections import deque

n, q = map(int, input().split())
ab = [[] for _ in range(n)]
px = [0 for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ab[a - 1].append(b - 1)
    ab[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    px[p - 1] += x

ans = px
queue = deque([(0, 0)])
while len(queue) > 0:
    prev, a = queue.pop()
    for c in ab[a]:
        if c != prev:
            ans[c] += ans[a]
            queue.append((a, c))

print(*ans)
### BUGGY CODE ###

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

a, b=[0], [0]
for i in range(N):
  a.append(a[i]+A[i])
  for i in range(M):
    b.append(b[i]+B[i])
    
ans, j=0, M
for i in range(N+1):
  if a[i]>K:
    break
  while b[j]>K-a[i]:
    j-=1
  ans=max(ans, i+j)
  
print(ans)

### FIXED CODE ###

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

a, b=[0], [0]
for i in range(N):
  a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])
    
ans, j=0, M
for i in range(N+1):
  if a[i]>K:
    break
  while b[j]>K-a[i]:
    j-=1
  ans=max(ans, i+j)
  
print(ans)
### BUGGY CODE ###

'''
考え方：
Eを0, Wを1と置くと、
0000000X11111111 と並ぶようにすればよい。
そのために、値を変える数が最小になるリーダーの位置を調べればよい

A. 全パターン試す
ある地点より左のWの数 + 右のEの数　の合計が最小になるパターンを求める（文字一致でカウント）
-> TLE

B. 全パターン
str.count('W')でやる
-> TLE

C. 「累積和」というアルゴリズムを使わないと解けない問題。学習して、使う！

'''

# from collections import deque # キュー、スタックに利用

# sys.stdin.readline() # 標準入力の高速化に利用
import sys
input = sys.stdin.readline

is_debug = True



def main():
    '''メイン処理'''
    n = int(input())
    s = input()

    s_list = list(s)

    sum_list = []
    for i in range(n):
        sum_list.append(s_list[:i].count('W') + s_list[i+1:].count('E'))
    
    print(min(sum_list))


if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()

### FIXED CODE ###

'''
制約
2 ≤ N ≤ 3×10^5(300,000)

入力例 3
8
WWWWWEEE

出力例 3
3

考え方：
Eを0, Wを1と置くと、
0000000X11111111 と並ぶようにすればよい。
そのために、値を変える数が最小になるリーダーの位置を調べればよい

-> 左端のW(West), 右端のE(East)はほぼ必ず向きを変える必要がある。


A. 全パターン試す
ある地点より左のWの数 + 右のEの数　の合計が最小になるパターンを求める（文字一致でカウント）
-> TLE

B. 全パターン
str.count('W')でやる
-> TLE

C. 「累積和」(cumulative sum)というアルゴリズムを使わないと解けない問題。学習して、使う！


'''

# from collections import deque # キュー、スタックに利用

# sys.stdin.readline() # 標準入力の高速化に利用
import sys
input = sys.stdin.readline

is_debug = False


def main():
    '''メイン処理'''
    n = int(input())
    sss = input()

    s_list = list(sss)

    W_sums = [0] * n # 累積和を入れるリスト
    E_sums = [0] * n # 累積和を入れるリスト
    W_sum = 0 # 左端から数えて、向きを変える必要のあるWの数
    E_sum = 0 # 右端から数えて、向きを変える必要のあるWの数
    
    if is_debug:
        print(W_sums)
    
    for i in range(n):
        if s_list[i] == 'W':
            W_sum += 1
        W_sums[i] = W_sum
        if s_list[n-i] == 'E':
            E_sum += 1
        E_sums[(n-1)-i] = E_sum

    if is_debug:
        print(W_sums)
        print(E_sums)
    
    # W_sums, E_sumsを用いて、向きを変える人数が最小となる値を見つける
    min_cost = float('inf')
    for i in range(n):
        # Wを振り向かせる人数
        if i == 0:
            W_cost = 0
        else:
            W_cost = W_sums[i-1]
        # Eを振り向かせる人数
        if i == n-1:
            E_cost = 0
        else:
            E_cost = E_sums[(i-1)+1]

        if is_debug:
            print(i, W_cost, E_cost)

        cost = W_cost+E_cost
        if cost < min_cost:
            min_cost = cost
    
    print(min_cost)

if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()
### BUGGY CODE ###

import sys
n, m = map(int, input().split())
G = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    cnt[a-1]+=1
    cnt[b-1]+=1
if any(cnt[i]%2 == 1 for i in range(n)):
    print('No')
    sys.exit()
c = cnt.count(4)
if any(cnt[i]>=6 for i in range(n)) or c>=3:
    print('Yes')
    sys.exit()
if c<1:
    print('No')
    sys.exit()
v = cnt.index(4)
used = [False]*n
for v0 in G[v]:
    now = v0
    used[v0] = True
    while True:
        for nv in G[now]:
            if used[nv]:
                continue
            now = nv
        if now == v0:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')
        

### FIXED CODE ###

import sys
n, m = map(int, input().split())
G = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    cnt[a-1]+=1
    cnt[b-1]+=1
if any(cnt[i]%2 == 1 for i in range(n)):
    print('No')
    sys.exit()
c = cnt.count(4)
if any(cnt[i]>=6 for i in range(n)) or c>=3:
    print('Yes')
    sys.exit()
if c<=1:
    print('No')
    sys.exit()
v = cnt.index(4)
for v0 in G[v]:
    now = v0
    p = v
    while True:
        for nv in G[now]:
            if nv == p:
                continue
            p = now
            now = nv
            break
        if now == v:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')
### BUGGY CODE ###

import sys
a=int(input())
t=True
i=0
while t:
  if ((a-i**5)**0.2)**5==a-i**5:
    print(i,int((-1)*(a-i**5)**0.2))
    sys.exit()
  i+=1

### FIXED CODE ###

import sys
a=int(input())
for i in range(151):
  b=i**5-a
  c=abs(b)
  j=0
  while j**5<=c:
    if j**5==c:
      if b>=0:
        print(i,j)
        sys.exit()
      else:
        print(i,-j)
        sys.exit()
    j+=1
### BUGGY CODE ###

from collections import Counter
N = input()
S=0
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S = int(X)*(10**(i))+S
  mod_val=(S % 2019)
  mod_count.append(mod_val)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))

### FIXED CODE ###

from collections import Counter
N = input()
S=0
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S = int(X)*pow(10,i,2019) % 2019
  S=mod_count[i]+S
  mod_count.append(S%2019)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))
### BUGGY CODE ###

from scipy.misc import comb

S = input()
N = len(S)
mod = 10 ** 9 + 7


ca = [0] * N
cq1 = [0] * N
if S[0] == 'A':
    ca[0] = 1
if S[0] == '?':
    cq1[0] = 1
for i in range(1, N):
    if S[i] == 'A':
        ca[i] = ca[i - 1] + 1
    else:
        ca[i] = ca[i - 1]
    if S[i] == '?':
        cq1[i] = cq1[i - 1] + 1
    else:
        cq1[i] = cq1[i - 1]

cc = [0] * N
cq2 = [0] * N
if S[-1] == 'C':
    cc[0] = 1
if S[-1] == '?':
    cq2[0] = 1
for i in range(1, N):
    if S[N - 1 - i] == 'C':
        cc[i] = cc[i - 1] + 1
    else:
        cc[i] = cc[i - 1]
    if S[N - 1 - i] == '?':
        cq2[i] = cq2[i - 1] + 1
    else:
        cq2[i] = cq2[i - 1]
cc = cc[::-1]
cq2 = cq2[::-1]

memo = {}
def f(q):
    if q in memo:
        return memo[q]
    x = [0] * (q + 1)
    for i in range(q + 1):
        x[i] = 2 ** (q - i) * comb(q, i, exact=True)
    memo[q] = x
    return x


memo2 = {}
def g(x, q):
    if (x, q) in memo2:
        return memo2[(x, q)]
    t = f(q)
    c = 0
    for i in range(q + 1):
        c += t[i] * (i + x)
    memo2[(x, q)] = c
    return c


ans = 0
for i in range(1, N - 1):
    if S[i] in ['B', '?']:
        ans += g(ca[i - 1], cq1[i - 1]) * g(cc[i + 1], cq2[i + 1])
print(ans % mod)


### FIXED CODE ###

S = input()
N = len(S)
mod = 10 ** 9 + 7

# dp[i][j]: i番目までの文字までで、状態jになる組み合わせ数
dp = [[0 for _ in range(4)] for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    if S[i] in ['A', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][1] += dp[i][0]
    if S[i] in ['B', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][2] += dp[i][1]
    if S[i] in ['C', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][3] += dp[i][2]

    for j in range(4):
        dp[i + 1][j] %= mod

print(dp[N][3])