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

N,C=map(int,input().split())
d=[list(map(int,input().split())) for i in range(C)]
c=[list(map(int,input().split())) for i in range(N)]
ans=10**18
mod0=[]
mod1=[]
mod2=[]
for i in range(N):
  for j in range(N):
    k=(i+j+2)%3
    if k==0:
      mod0.append((i,j))
    elif k==1:
      mod1.append((i,j))
    else:
      mod2.append((i,j))
ans=10**18
for c0 in range(1,C+1):
  for c1 in range(1,C+1):
    for c2 in range(1,C+1):
      if c1==c2 or c2==c0 or c0==c1:
        continue
      cnt=0
      for x,y in mod0:
        cnt+=d[c[x][y]-1][c0-1]
      for x,y in mod1:
        cnt+=d[c[x][y]-1][c1-1]
      for x,y in mod2:
        cnt+=d[c[x][y]-1][c2-1]
      ans=min(ans,cnt)
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,C=map(int,input().split())
d=[list(map(int,input().split())) for i in range(C)]
c=[list(map(int,input().split())) for i in range(N)]
ans=10**18
mod0=[]
mod1=[]
mod2=[]
for i in range(N):
  for j in range(N):
    k=(i+j+2)%3
    if k==0:
      mod0.append((i,j))
    elif k==1:
      mod1.append((i,j))
    else:
      mod2.append((i,j))
cnt0=[0]*(C+1)
cnt1=[0]*(C+1)
cnt2=[0]*(C+1)
for c0 in range(1,C+1):
  for x,y in mod0:
    cnt0[c0]+=d[c[x][y]-1][c0-1]
for c1 in range(1,C+1):
  for x,y in mod1:
    cnt1[c1]+=d[c[x][y]-1][c1-1]
for c2 in range(1,C+1):
  for x,y in mod2:
    cnt2[c2]+=d[c[x][y]-1][c2-1]
ans=10**18
for c0 in range(1,C+1):
  for c1 in range(1,C+1):
    for c2 in range(1,C+1):
      if c1==c2 or c2==c0 or c0==c1:
        continue
      cnt=cnt0[c0]+cnt1[c1]+cnt2[c2]
      ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

from functools import reduce


def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a % b)


def gcd(num):
    return reduce(euclid, num)


k = int(input())
ans = 0
i_list = []

for i1 in range(1, k+1):
    for i2 in range(1, k+1):
        for i3 in range(1, k+1):
            ans += gcd([i1, i2, i3])

print(ans)


### FIXED CODE ###

from functools import reduce


def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a % b)


def gcd(num):
    return reduce(euclid, num)


k = int(input())
ans = 0
i_list = []

for i1 in range(1, k+1):
    for i2 in range(1, k+1):
        for i3 in range(1, k+1):
            ans += gcd([i1, i2, i3])

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

import numpy as np
inp1 = input().split()
inp2 = input().split()

a = int(inp1[0])
b = np.array(inp2).astype(int)
ansno = a
maxno = b[0]

ii = 0
for i in b:
  bslice = b[:ii+1]
  if min(bslice) != i:
    ansno -=1
  ii+=1
print(ansno)


### FIXED CODE ###

n = int(input())
m = input().split()
ppp = list(map(int, m))
max = 2*10**5+1
ans = 0
for p in ppp:
    if p < max:
        ans += 1
        max = p
print(ans)
### BUGGY CODE ###

import collections
N = (int(input()))

ans = 0
counter_list = []

for _ in range(N):
    s = input()
    c = collections.Counter(s)
#    print(c)
#    print(counter_list)
    ans += counter_list.count(c)

    counter_list.append(c)

print(ans)

### FIXED CODE ###

import collections
N = (int(input()))

ans = 0
counter_list = []

for _ in range(N):
    s = input()
    counter_list.append("".join(sorted(s)))

ans = 0
wordcount = {}
for word in counter_list:
    if word in wordcount:
        wordcount[word] += 1
        ans += (wordcount[word])
    else:
        wordcount[word] = 0

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

#!/usr/bin/env python3
 
# 以下を記述しないとTLEになる, 何故？
import collections
import itertools
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

def sol():
    S = input()
    T = input()

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

    for i, s in enumerate(S):
        posS[s].append(i)

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()
### BUGGY CODE ###



def p(k,w,maxP):
    count = 1
    tmpList = []
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
        else:
            count += 1
            tmpList = []
            tmpList.append(x)
    
    if count > k :
        result = False
    else:
        result = True

    return result


def pout(k,w,maxP):
    count = 1
    tmpList = []
    mP = 0
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
        else:
            count += 1
            tmpList = []
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
    
    if count > k :
        result = False
    else:
        result = True

    return result, count, mP


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


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)+5
rangeMin = 1

while _:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == False and p(k,w,rangeMid+1) == False:
        rangeMin = rangeMid
    elif p(k,w,rangeMid) == True and p(k,w,rangeMid+1) == True:
        rangeMax = rangeMid
    else:
        break

print(pout(k,w,rangeMid+1)[2])

### FIXED CODE ###



def p(k,w,maxP):
    count = 1
    tmpWeight = 0
    for x in w:
        if tmpWeight+x <= maxP:
            tmpWeight += x
        else:
            count += 1
            if count > k :
                return False
            tmpWeight = x
    

    return True




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


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)
### BUGGY CODE ###

import numpy as np

L, R = map(int, input().split())

min_ = np.inf
for i in range(L, R):
    for j in range(i + 1, R + 1):
        if (i * j) % 2019 <= min_:
            min_ = (i * j) % 2019

print(min_)

### FIXED CODE ###

import numpy as np

L, R = map(int, input().split())

min_ = np.inf
for i in range(L, R):
    for j in range(i + 1, R + 1):
        if (i * j) % 2019 <= min_:
            min_ = (i * j) % 2019
            if min_ == 0:
                print(min_)
                exit()

print(min_)
### BUGGY CODE ###

# import queue
# from collections import deque

h, w = map(int, input().split())

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

# q = deque()
q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.append((i, j))

cnt = 0
while q:
    qq = []
    for (i, j) in q:
        # i, j = q.pop()
        if not grid[i + 1][j]:
            grid[i + 1][j] = True
            qq.append((i + 1, j))
        if not grid[i - 1][j]:
            grid[i - 1][j] = True
            qq.append((i - 1, j))
        if not grid[i][j + 1]:
            grid[i][j + 1] = True
            qq.append((i, j + 1))
        if not grid[i][j - 1]:
            grid[i][j - 1] = True
            qq.append((i, j - 1))

    cnt += 1
    q = qq

print(cnt - 1)


### FIXED CODE ###

h, w = map(int, input().split())

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.append((i, j))

cnt = 0
while q:
    qq = []
    for i, j in q:
        if not grid[i + 1][j]:
            grid[i + 1][j] = True
            qq.append((i + 1, j))
        if not grid[i - 1][j]:
            grid[i - 1][j] = True
            qq.append((i - 1, j))
        if not grid[i][j + 1]:
            grid[i][j + 1] = True
            qq.append((i, j + 1))
        if not grid[i][j - 1]:
            grid[i][j - 1] = True
            qq.append((i, j - 1))

    cnt += 1
    q = qq

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

n=int(input())
a=[sorted(list(str(input())))for _ in range(n)]
ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        if a[i] == a[j]:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
c = Counter([''.join(sorted(input())) for i in range(n)])
 
ans = 0
for k, cnt in c.items():
    ans+=cnt*(cnt-1)//2
print(ans)
### BUGGY CODE ###

N,K,L=map(int,input().split())
PQ=[list(map(int,input().split())) for i in range(K)]
RS=[list(map(int,input().split())) for i in range(L)]

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
    
def UF_make(graph,n):
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):
        Root[i] = find_root(Root,i)
    Root.pop(0)  #
    return Root

PQN=UF_make(PQ,N)
RSN=UF_make(RS,N)
PQRS=[PQN[i]*10**6+RSN[i] for i in range(N)]
ans=[1]*N
for i in range(N):
    ans[i]=PQRS.count(PQRS[i])
print(*ans)

### FIXED CODE ###

N,K,L=map(int,input().split())
PQ=[list(map(int,input().split())) for i in range(K)]
RS=[list(map(int,input().split())) for i in range(L)]

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
    
def UF_make(graph,n):
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):
        Root[i] = find_root(Root,i)
    Root.pop(0)  #
    return Root

PQN=UF_make(PQ,N)
RSN=UF_make(RS,N)
PQRS=[PQN[i]*10**6+RSN[i] for i in range(N)]
D=len(set(PQRS))
PQRS=[[PQRS[i],i,0] for i in range(N)]
PQRS.sort()

p=0
while p<N:
    i=1
    c=0
    if p+i>N-1:
        break
    while PQRS[p][0]==PQRS[p+i][0]:
        c+=1
        i+=1
        if p+i>N-1:
            break
    for j in range(p,p+i):
        PQRS[j][2]=c
    p+=i
PQRS.sort(key=lambda x:x[1])
for i in range(N):
    print(PQRS[i][2]+1,end=' ')
### BUGGY CODE ###

N, W = map(int, input().split())
wv_list = [[int(i) for i in input().split()] for _ in range(N)]

dp = [[-1 for i in range(W+1)] for _ in range(N)]

w = wv_list[0][0]
v = wv_list[0][1]
dp[0][w] = v

for i in range(1, N):
    w = wv_list[i][0]
    v = wv_list[i][1]
    
    for j in range(W+1):
        if j < w:
            dp[i][j] = dp[i-1][j]
        elif j == w:
            dp[i][j] = max(dp[i-1][j], v)
        else:
            if dp[i-1][j-w] == -1:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

print(max(dp[-1]))

### FIXED CODE ###

import numpy as np

n, w = map(int, input().split())
wv_list = [[int(i) for i in input().split()] for i in range(n)]

dp = np.zeros(w+1)

for wv in wv_list:
    w = wv[0]
    v = wv[1]
    dp[w:] = np.maximum(dp[:-w]+v, dp[w:])

print(int(np.max(dp)))
### BUGGY CODE ###

# input
N, M = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[None for __ in range(N*max(V)+1)] for _ in range(N+1)]
dp[0] = [10**9 for _ in range(N*max(V)+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for v in range(N*max(V)+1):
        if V[i-1] >= v:
            dp[i][v] = min(dp[i-1][v], W[i-1])
        else:
            dp[i][v] = min(dp[i-1][v], dp[i-1][v-V[i-1]] + W[i-1])


print(max(i for i, w in enumerate(dp[-1]) if w <= M))


### FIXED CODE ###

# input
N, M = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[None for __ in range(N*max(V)+1)] for _ in range(N+1)]
dp[0] = [10**9 for _ in range(N*max(V)+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for v in range(N*max(V)+1):
        if V[i-1] >= v:
            dp[i][v] = min(dp[i-1][v], W[i-1])
        else:
            dp[i][v] = min(dp[i-1][v], dp[i-1][v-V[i-1]] + W[i-1])


print(max(i for i, w in enumerate(dp[-1]) if w <= M))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
setA = list(set(A))
setN = len(setA)
countA = [A.count(a) for a in setA]
ansA = [countA[i]*(countA[i]-1)//2 for i in range(setN)]
sumA = sum(ansA)

for i in range(N):
  index = setA.index(A[i])
  ans = sumA - ansA[index] + (countA[index] -1) * (countA[index] -2) //2
  print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
countA = Counter(A)
ansA = [v*(v-1)//2 for k,v in countA.items()]
sumA = sum(ansA)

for i in range(N):
  t =  countA[A[i]]
  ans = sumA - t*(t-1)//2 + (t-1)*(t-2)//2
  print(ans)
### BUGGY CODE ###

def cnt(l, r, x):
    if r == n - 1:
        return 1
    t = (l, r, x)
    if t in memo:
        return memo[t]
    re = 0
    dpi = dp[r + 1]
    for j in range(r + 1, n):
        if dpi[j] == x:
            re += cnt(r + 1, j, x)
    memo[t] = re
    return re

memo = {}
md = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]
for i, dpi in enumerate(dp):
    s = dpi[i]
    for j in range(i + 1, n):
        dpi[j] = s = s ^ a[j]
ans = 0
for r in range(n):
    ans = (ans + cnt(0, r, dp[0][r])) % md
print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md=10**9+7
    n=II()
    aa=LI()
    cs=[0]
    for a in aa:cs.append(cs[-1]^a)
    #print(cs)

    cnt={}
    cnt0=[1]*len(cs)
    for i,s in enumerate(cs[1:],1):
        if s==0:
            cnt0[i]=cnt0[i-1]+1
        elif s in cnt:
            cnt0[i]=cnt0[i-1]
            c0=cnt0[i]-cnt0[cnt[s][2]]
            cnt[s][0]=(cnt[s][0]+cnt[s][1]*c0)%md
            cnt[s][1]=(cnt[s][1]+cnt[s][0])%md
            cnt[s][2]=i
        else:
            cnt0[i]=cnt0[i-1]
            cnt[s]=[1,1,i]
    #print(cnt)
    #print(cnt0)

    if cs[-1]==0:ans=sum(v[1] for v in cnt.values())+pow(2,cnt0[-1]-2,md)
    else:ans=cnt[cs[-1]][0]
    print(ans%md)

main()
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline
def main():
  a=int(input())
  b=[[]for i in range(a)]
  for i in range(a):
    b[i]=deque(list(map(int,input().split())))
  c=[[]for i in range(a)]
  ans=0
  d=[0 for i in range(a)]
  while sum(len(v) for v in b)!=0:
    f=[0 for i in range(a)]
    ans+=1
    T=0
    for i in range(a):
      if d[i]==0 and f[i]==0 and len(b[i])>0:
        e=b[i][0]-1
        if e in c[i]:
          c[i].pop(c[i].index(e))
          T=1
          b[e].popleft()
          b[i].popleft()
          d[i]=0
          d[e]=0
          f[i]=1
          f[e]=1
        else:
          c[e].append(i)
          d[i]=1
    if T==0:
      print(-1)
      exit()
      
      
  print(ans)  
if __name__ == '__main__':  
  main()      

        




### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
def main():
  a=int(input())
  b=[[]for i in range(a)]
  for i in range(a):
    b[i]=deque(list(map(int,input().split())))
  c=[[]for i in range(a)]
  ans=0
  d=[i for i in range(a)]
  while d:
    nextd=[]
    f=set()
    ans+=1
    T=0
    for i in d:
      if i not in f and len(b[i])>0:
        e=b[i][0]-1
        if e in c[i]:
          c[i].pop(c[i].index(e))
          T=1
          b[e].popleft()
          b[i].popleft()
          if len(b[i])>0:
            nextd.append(i)
          if len(b[e])>0:
            nextd.append(e)
          f|={i,e}
        else:
          c[e].append(i)
    if T==0:
      print(-1)
      exit()
    d=nextd
      
      
  print(ans)  
if __name__ == '__main__':  
  main()
### BUGGY CODE ###

# a^n mod p
def beki_mod(a, n, p):
    ans = 1
    n = format(n, "b")
    for i in range(len(n)):
        ans = ans * ans % p
        if n[i] == "1":
            ans = ans * a % p
    return ans

# a! mod p
def kaijo_mod(a, p):
    ans = 1
    while a > 0:
        ans = ans * a % p
        a -= 1
    return ans    

# nCr = n * (n -1) * ... * (n - r + 1) / r!
# a^(-1) mod p = a^(p -2) mod p
def combi_mod(n, r, p):
    bunshi = 1
    r = min(r, n - r)

    bumbo = kaijo_mod(r, p)
    bumbo_gyakugen = beki_mod(bumbo, p - 2, p)

    while r > 0:
        bunshi = bunshi * n % p
        n -= 1
        r -= 1
    
    ans = bunshi * bumbo_gyakugen % p
    return ans


H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7

if B < W / 2:
    not_ans = 0
    total = combi_mod((H - 1) + (W - 1), H-1, mod)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h -1) + (sq1w - 1), (sq1h -1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod) % mod
        not_ans += n
    ans = (total - not_ans) % mod
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h - 1) + (sq1w - 1), (sq1h - 1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod)
        ans += n
    ans %= mod
    print(ans)


### FIXED CODE ###

mod = 10 ** 9 + 7
N = 10 ** 6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append(fact[-1] * i % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

def combi_mod(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


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

if B < W / 2:
    not_ans = 0
    total = combi_mod((H - 1) + (W - 1), H-1, mod)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h -1) + (sq1w - 1), (sq1h -1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod) % mod
        not_ans = (not_ans + n) % mod
    ans = (total - not_ans) % mod
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h - 1) + (sq1w - 1), (sq1h - 1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod)
        ans = (ans + n) % mod
    ans %= mod
    print(ans)
### BUGGY CODE ###

n = int(input())
ss = []
mylist =[]
for i in range(n):
    temp = input()
    ss.append(temp)
    
cnt = 0
for s in ss:
    if s in mylist:
        next
    else:
        mylist.append(s)
        cnt += 1
        
print(cnt)

### FIXED CODE ###

n = int(input())
ss = set()
for i in range(n):
    temp = input()
    if temp in ss:
        next
    else:
        ss.add(temp)
        
print(len(ss))
### BUGGY CODE ###

def func(s):
    alpha = [0, 0, 0]
    ques = 0
    ab = 0  # ABの選び方
    count = 0

    for _s in s:
        if _s == "?":
            # ある?(== C)を末尾とするABCの選び方は
            # 「ABの選び方+?」
            count *= 3
            count += ab
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            ab += alpha[0] * (3**ques)
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            ques += 1
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            ab += alpha[0] * (3**ques)
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        count %= (10 ** 9 + 7)
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


# print(func("A??C") == 8)
# print(func("ABCBC") == 3)
# print(func("????C?????B??????A???????") == 979596887)
print(func(input()))


### FIXED CODE ###

def func(s):
    alpha = [0, 0, 0]
    ques = 0
    nowQues = 1
    ab = 0  # ABの選び方
    count = 0
    for _s in s:
        if _s == "?":
            count *= 3  # 既にabcとなっている場合の数
            count += ab  # 「? == c」とする場合
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            if ques > 0:
                ab += alpha[0] * nowQues*3  # (3 ** ques)
            else:
                ab += alpha[0]
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * nowQues  # (3 ** (ques - 1))
            ques += 1
            if ques > 1:
                nowQues *= 3
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            if ques > 0:
                ab += alpha[0] * nowQues*3  # (3 ** ques)
            else:
                ab += alpha[0]
            if ques > 0:
                ab += ques * nowQues  # (3 ** (ques - 1))
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        count %= 10 ** 9 + 7
        ab %= 10 ** 9 + 7
        nowQues %= 10 ** 9 + 7
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


"""
print(func("A??C") == 8)
print(func("ABCBC") == 3)
print(func("????C?????B??????A???????") == 979596887)
def listToString(_list, split=""):
    maped_list = map(str, _list)  # mapで要素すべてを文字列に
    mojiretu = split.join(maped_list)
    return mojiretu
print(func(listToString(["?" for _ in range(10 ** 5)])))
print("finish")
"""
print(func(input()))
### BUGGY CODE ###

n = int(input())
mod = 10**9 + 7

if n == 1:
    print(0)
    exit()

dp = [[0]*4 for _ in range(n+1)]

dp[2][0] = 64
dp[2][1] = 17
dp[2][2] = 17
dp[2][3] = 2
for i in range(2, n):
    dp[i+1][3] = ((dp[i][1] + dp[i][2]) % mod + dp[i][3]*10 % mod) % mod

    dp[i+1][1] = (dp[i][0] + dp[i][1]*9 % mod) % mod

    dp[i+1][2] = (dp[i][0] + dp[i][2]*9 % mod) % mod

    dp[i+1][0] = (dp[i][0]*8) % mod
print(dp[n][3])

### FIXED CODE ###

n = int(input())
mod = 10**9 + 7

if n == 1:
    print(0)
    exit()

dp = [[0]*4 for _ in range(n+1)]

dp[2][0] = 64
dp[2][1] = 17
dp[2][2] = 17
dp[2][3] = 2
for i in range(2, n):
    dp[i+1][3] = ((dp[i][1] + dp[i][2]) % mod + dp[i][3]*10 % mod) % mod

    dp[i+1][1] = (dp[i][0] + dp[i][1]*9 % mod) % mod

    dp[i+1][2] = (dp[i][0] + dp[i][2]*9 % mod) % mod

    dp[i+1][0] = (dp[i][0]*8) % mod
print(dp[n][3])
### BUGGY CODE ###

N=int(input())
s=[]
cnt=0
for i in range(N):
    s.append(input())
s=list(map(sorted,s))
while len(s)>0:
    cnt+=s.count(s.pop(0))
print(cnt)

### FIXED CODE ###

N=int(input())
dic={}
cnt=0
for i in range(N):
    temp=' '.join(sorted(input()))
    if temp in dic:
        dic[temp]+=1
    else:
        dic[temp]=1
for k,v in dic.items():
    cnt+=v*(v-1)//2
print(cnt)