Harryxun/stf_run huggingface dataset:
n,x = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
for i in range(N):
  if A[i] > x :
    print(ans)
    break
  else:
    x -= A[i]
    if i == N-1:
      print(N-1)
      break

### FIXED CODE ###

N,x = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
ans = 0
for i in range(N):
  if A[i] <= x:
    if i == N-1:
      if x == A[i]:
        ans += 1
    else:
      x -= A[i]
      ans += 1
  else:
    break
print(ans)
c = [1]*("z".encode()-"a".encode()+1)
for x in map(lambda x: x-"a".encode(), input().encode()):
	c[x] += 1

m = 1
for x in c:
  m *= c

print(m-1)


### FIXED CODE ###

N = input()
c = [1]*("z".encode()[0]-"a".encode()[0]+1)
for x in map(lambda x: x-"a".encode()[0], input().encode()):
	c[x] += 1

m = 1
for x in c:
  m = (m * x) % (1e9+7)

print("{:.0f}".format(m-1))
# 2入力
H, W = map(int, input().split())

if H == 1 or W == 1:
    pirnt(1)
else:
    mass = 0
    if W % 2 != 0:
        if H % 2 != 0:
            mass += (int(H / 2) + 1) * (int(W / 2) + 1)
            mass += (int(H / 2)) * (int(W / 2))
            print(mass)
        else:
            mass += (int(H / 2)) * (int(W / 2) + 1)
            mass += (int(H / 2)) * (int(W / 2))
            print(mass)

    else:
        if H % 2 != 0:
            mass += (int(H / 2) + 1) * (int(W / 2))
            mass += (int(H / 2)) * (int(W / 2))
            print(mass)
        else:
            mass += (int(H / 2)) * (int(W / 2))
            mass += (int(H / 2)) * (int(W / 2))
            print(mass)

### FIXED CODE ###

# 2入力
H, W = map(int, input().split())

if H == 1 or W == 1:
    print(1)
else:
    mass = 0
    if W % 2 != 0:
        if H % 2 != 0:
            mass += (int(H / 2) + 1) * (int(W / 2) + 1)
            mass += (int(H / 2)) * (int(W / 2))
            print(mass)
        else:
            mass += (int(H / 2)) * (int(W / 2) + 1)
            mass += (int(H / 2)) * (int(W / 2))
            print(mass)

    else:
        if H % 2 != 0:
            mass += (int(H / 2) + 1) * (int(W / 2))
            mass += (int(H / 2)) * (int(W / 2))
            print(mass)
        else:
            mass += (int(H / 2)) * (int(W / 2))
            mass += (int(H / 2)) * (int(W / 2))
            print(mass)
import math

s = input().split()

a = int(s[0])
b = int(s[1])
c = int(s[2])

#if math.sqrt(a) + math.sqrt(b) < math.sqrt(c) :
if (a + b + 2* math.sqrt(a*b) ) < c :
  print('Yes')
else:
  print('No')


### FIXED CODE ###

d = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
str_n = input()
n = int(str_n)
print(d[n-1])
a = []
while 1:
 s = input()
 if s == 'END_OF_TEXT':
  break
 else:
  s = list(s.split('.'))
  s.remove('')
  s = list(s[0].split())
  a.append(s)

print(a.count(a[0]) - 1)

### FIXED CODE ###

word = input()
counter = 0
while 1:
 s = input()
 if s == 'END_OF_TEXT':
  break
 else:
  s = list(s.lower().split())
  counter += s.count(word)
  counter += s.count(word + '.')

print(counter)
N, M = map(int, input().split())
l1 = []
l2 = []
ans = 0
rest = M
for i in (N+1):
	l1[i],l2[i]  = map(int, input().split())

while true:
	min_index = l1.index(min(l1))
	ans += (min(l1) * l2[min_index])
	rest -= l2[min_index]
	if rest == 0:
		break
	l1.pop(min_index)

print(ans)

### FIXED CODE ###

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

total = H* W
ans = total - (H*w + W*h - h*w) 
print (ans)
N = input()

i = N + 1
while True:
    if(i % 2 == 0 and i % N == 0):
        break
    i = i + 1

print(i)


### FIXED CODE ###


N = int(input())

if(N % 2 == 0):
    print(N)
else:
    print(2 * N)
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
field = []
H, W = 0, 0
q = queue.Queue()

def solver(x, y, symbol):
  global q, field, H, W
  while True:
    if x < 0 or y < 0 or x >= H or y >= W:
      continue
    for dx, dy in dxy:
      if x+dx < 0 or y+dy < 0 or x+dx >= H or y+dy >= W:
        continue
      if field[x+dx][y+dy] == symbol:
        field[x+dx][y+dy] = '.'
        q.put([x+dx, y+dy])
    data = q.get()
    if data is None:
      return
    x, y = data)

while True:
  H, W = map(int, raw_input().split())
  if H == 0 and W == 0:
    break
  field = [list(raw_input()) for i in range(H)]

  ans = 0
  for x in xrange(H):
    for y in xrange(W):
      if field[x][y] != '.':
        solver(x, y, field[x][y])
        ans += 1
  print ans

### FIXED CODE ###

import Queue

dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
field = []
H, W = 0, 0
q = Queue.Queue()

def solver(x, y, symbol):
  global q, field, H, W
  while True:
    if x < 0 or y < 0 or x >= H or y >= W:
      continue
    for dx, dy in dxy:
      if x+dx < 0 or y+dy < 0 or x+dx >= H or y+dy >= W:
        continue
      if field[x+dx][y+dy] == symbol:
        field[x+dx][y+dy] = '.'
        q.put([x+dx, y+dy])
    if q.empty():
      return
    x, y = q.get()

while True:
  H, W = map(int, raw_input().split())
  if H == 0 and W == 0:
    break
  field = [list(raw_input()) for i in range(H)]

  ans = 0
  for x in xrange(H):
    for y in xrange(W):
      if field[x][y] != '.':
        solver(x, y, field[x][y])
        ans += 1
  print ans
N, K = map(int, input().split())
h = [int(input()) for i in range(N)]

# 小さい順にソートする
#def sort(h):
#    if len(h) <= 1:
        return h
#    base = h[-1]
#    low_temp = [];
#    high_temp = [];
#    base_count = 1
#    for i in range(len(h)-1):
#        if h[i] < base:
#            low_temp.append(h[i])
#        elif h[i] > base:
#            high_temp.append(h[i])
#        else:
#            base_count += 1
#    low = sort(low_temp)
#    high = sort(high_temp)
#    return low + [base]*base_count + high

h.sort()
hantei = 10**10
for i in range(N-K+1):
    temp = h[i:i+K]
    temp_dif = max(temp) - min(temp)
    if temp_dif < hantei:
        hantei = temp_dif

print(hantei)


### FIXED CODE ###

D = int(input())
if D == 25:
  print("Christmas")
elif D == 24:
  print("Christmas Eve")
elif D == 23:
  print("Christmas Eve Eve")
else:
  print("Christmas Eve Eve Eve")
w = []
v = []
n, W = map(int, input().split())
#dp = [[0 for i in range(n)] for j in range(W)]
dp = [[None for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    v1, v2 = map(int, input().split())
    w.append(v1)
    v.append(v2)

# i: Index (Tracing all items)
# j: Remaining weight
# Return the sum of value
def knap(i, j):
    # print("\n# i: " + str(i))
    # print("# j: " + str(j))
    if dp[i][j] is not None:
        return dep[i][j]

    res = 0

    if i == n:
#        dp[i][j] = 0
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        # if dp[i][j] is None:
        #     dp[i][j] = dp[i-1][j] + v[i]
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]
#    return res

print(knap(0, W))


### FIXED CODE ###

n, W = map(int, input().split())
w = [0]*(n+1)
v = [0]*(n+1)

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[0 for i in range(W+1)] for j in range(n+1)]

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

def knap(i, j):
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
       	res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]

for i in reversed(range(n)):
    for j in range(W+1):
#        res = 0
        # if i == n-1:
        #     res = 0
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])

#print(knap(0, W))
print(dp[0][W])
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1

### FIXED CODE ###

n=int(input())
#a=[0,a1,a2,a3,...,an]
a=[0]
b=[0]
c=[0]
#０日め　0,0,0
#1日目　a1,b1,c1
#2日目　a2=b1+a2 or c1+a2
dp=[[0 for i in range(3)] for j in range(n+1)]
for i in range(n):
    x,y,z=map(int,input().split())
    a.append(x)
    b.append(y)
    c.append(z)
for i in range(1,n+1):
    dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][2]+a[i])
    dp[i][1]=max(dp[i-1][0]+b[i],dp[i-1][2]+b[i])
    dp[i][2]=max(dp[i-1][0]+c[i],dp[i-1][1]+c[i])
print(max(dp[n]))
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]
parent = {i:i for i in range(1, n+1)}
sizes = {i:1 for i in range(1, n+1)}
counts = {i:0 for i in range(1, n+1)}
howmanydisses = {i:0 for i in range(1, n+1)}

def f(parent, a):
	if parent[a] != a:
		parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	pa,pb = f(parent, a), f(parent, b)
	counts[a] +=1
	counts[b] +=1
	if pa != pb:
		parent[pb] = pa
		sizes[pa] += sizes[pb]

for a,b in disses:
	pa,pb = f(parent, a), f(parent, b)
	if pa == pb:
		howmanydisses[a] += 1
		howmanydisses[b] += 1

print ' '.join([str(sizes[f(parent,a)] - counts[a] - howmanydisses[a] - 1)  for a in range(1, n+1)])

### FIXED CODE ###

import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(0, n+1)}
sizes = {i:1 for i in range(0, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, u):
	if parent[u] != u: 
		parent[u] = f(parent, parent[u])
	return parent[u]

for a,b in friendships:
	if a == b: continue

	pa,pb = f(parent, a), f(parent, b)
	
	adj[a].add(b)
	adj[b].add(a)

	if pa != pb:
		if sizes[pa] >= sizes[pb]:
			parent[pb] = pa
			sizes[pa] += sizes[pb]
		else:
			parent[pa] = pb
			sizes[pb] += sizes[pa]

for c,d in disses:
	pc,pd = f(parent, c), f(parent, d)
	if (pc == pd):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])
x = input()
y = [input() for i + 1 in range(x)]
z = y.split()
s = Case
count = 1
  
for a in range(1,10001):
    print('{} {} : {}',format(s,count,z))
    count += 1

### FIXED CODE ###

i = 1
while True:
     x = int(input())
     if x == 0: break
     print('Case {}: {}'.format(i, x))
     i += 1
def readinput():
    n,m=list(map(int,input().split()))
    a=[]
    for _ in range(m):
        a.append(int(input()))
    return n,a

def main(n,a):
    nroute=[0]*(n+1)
    nroute[0]=0
    nroute[1]=1
    nroute[2]=1
    for i in range(3,n+1):
        nroute[i]=nroute[i-1]+nroute[i-2]
    #print(nroute)
    
    subn=[]
    i=0
    for j in a:
        subn.append((i,j-1))
        i=j+1
    subn.append((i,n))
    #print(subn)

    MOD=10**9+7
    nways=1
    for i,j in subn:
        l=j-i+1
        nways=nways*nroute[l]%MOD

    return nways

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(ans)



### FIXED CODE ###

def readinput():
    n,m=list(map(int,input().split()))
    a=[]
    for _ in range(m):
        a.append(int(input()))
    return n,a

def main(n,a):
    MOD=10**9+7

    nroute=[0]*(n+2)
    nroute[0]=0
    nroute[1]=1
    nroute[2]=1
    for i in range(3,n+2):
        nroute[i]=(nroute[i-1]+nroute[i-2])%MOD
    #print(nroute)
    
    subn=[]
    i=0
    for j in a:
        subn.append((i,j-1))
        i=j+1
    subn.append((i,n))
    #print(subn)

    nways=1
    for i,j in subn:
        l=j-i+1
        nways=nways*nroute[l]%MOD

    return nways

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(ans)
K = int(input())
S = input()
X = len(S)
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

ans = 0
for i in range(X,K+X+1):
    temp = 1
    A = i-X
    B = K+X-i
    temp *= cmb(A+X-1,X-1,mod)*power(25,A,mod)
    temp %= mod
    temp *= power(26,B,mod)
    ans += temp
    ans %= mod
print(ans)

### FIXED CODE ###

K = int(input())
S = input()
X = len(S)
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


A = 0
B = K
temp = cmb(A+X-1,X-1,mod)*power(25,A,mod)
temp %= mod
temp *= power(26,B,mod)
temp %= mod

ans = temp

for i in range(X+1,K+X+1):

    temp *= 25
    temp %= mod
    
    temp *= pow(26, mod-2, mod)
    temp %= mod
    
    temp *= i-1
    temp %= mod
    
    temp *= pow(i-X, mod-2, mod)
    temp %= mod    

    ans += temp
    ans %= mod

print(ans)
def func(a):
    if (a==0):
        return 6
    else:
        return func(a-1)+2
N=int(input())

S=10**9+7
if N==1:
    z=0
elif N==2:
    z=2
else:
    z=((10**(N-2) *N*2) - (10**(N-3) * (func(N-3)))) %S
print(z)



### FIXED CODE ###

N=int(input())
MOD=10**9+7
if N==1:
    z=0
else:
    z = 10**N - (9**N *2) + 8**N
    z %= MOD
print(z)
N,H,W = map(int, raw_input().split())
for i in range(N):
    a.append(list(map(int, input().split())))

num =0
for i in range(N):
    if a[i][0]>=H:
        if a[i][1] >= W:
            num +=1
print(num) 

### FIXED CODE ###

a =[]
N,H,W = map(int, input().split())
for i in range(N):
    a.append(list(map(int, input().split())))

num =0
for i in range(N):
    if a[i][0]>=H:
        if a[i][1] >= W:
            num +=1
print(num)
r = int(input())
p = 3.141592
print(r*r*p,2*r*p)

### FIXED CODE ###

import math
r = float(input())
p = math.pi
print(round(r*r*p,6),round(2*r*p,6))
s=input()

arr=[]
tmp=''
for s_ in s:
  if s_ in ('A', 'C', 'G', 'T'):
    tmp+=s_
  else:
    arr.append(len(tmp))
    tmp=''
print(max(arr))

### FIXED CODE ###

s=input()

cnt=0
max_val=0
for s_ in s:
  if s_ in ('A', 'C', 'G', 'T'):
    cnt+=1
  else:
    cnt=0
  max_val=max(cnt, max_val)
print(max_val)
N = int(input()) 
A = list(map(int, input().split())) 

M = 1000
X = 0

for i in range(N-1):
    if A[i] < A[i+1]:
        X = int(M/A[i])
        M = int(M - X * A[i])
    
	M = M + X * A[i+1]

print(int(M))


### FIXED CODE ###

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

M = 1000
X = 0

for i in range(N-1):
    if A[i] < A[i+1]:
        X = int(M/A[i])
        M = int(M - X * A[i])
    
    M = M + X * A[i+1]
    X = 0

print(int(M))
x,y,a,b,c=map(int,input().split())
lia=list(map(int,input().split()))
lib=list(map(int,input().split()))
lic=list(map(int,input().split()))
lia.sort(reverse=True)
lib.sort(reverse=True)
lic.sort(reverse=True)
ans=lia[:x]+lib[:y]
ans.sort(reverse=True)
cnt=0
now=0
while cnt < a+b and now < c:
  if lic[now] > ans[cnt]:
    ans[cnt]=lic[now]
    now+=1
  cnt+=1
print(sum(ans))

### FIXED CODE ###

x,y,a,b,c=map(int,input().split())
lia=list(map(int,input().split()))
lib=list(map(int,input().split()))
lic=list(map(int,input().split()))
lia.sort(reverse=True)
lib.sort(reverse=True)
lic.sort(reverse=True)
ans=lia[:x]+lib[:y]
ans.sort()
cnt=0
now=0
while cnt < x+y and now < c:
  if lic[now] > ans[cnt]:
    ans[cnt]=lic[now]
    now+=1
  cnt+=1
print(sum(ans))
import sys
readline = sys.stdin.readline

def score(A):
    t = 0
    for ai,bi,ci,di in zip(a,b,c,d):
        if A[bi]-A[ai]==ci:
            t += di
    return t

def dfs(A):
    if len(A)==n:
        return score(A)
    ans = 0
    prev_last = A[-1] if len(A)>0 else 0
    for v in range(prev_last, m):
        A.append(v)
        ans = max(ans, dfs(A))
        A.pop()
    return ans

n, m, q = map(int, readline().split())
A,B,C,D = [0]*q, [0]*q, [0]*q, [0]*q
for i in range(q):
    a,b,C[i],D[i] = map(int, readline().split())
    A[i] = a-1
    B[i] = b-1

print(dfs([]))

### FIXED CODE ###

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

def score(Ans):
    t = 0
    for ai,bi,ci,di in zip(A,B,C,D):
        if Ans[bi]-Ans[ai]==ci:
            t += di
    return t

def dfs(Ans):
    if len(Ans)==n:
        return score(Ans)
    ans = 0
    prev_last = Ans[-1] if len(Ans)>0 else 0
    for v in range(prev_last, m):
        Ans.append(v)
        ans = max(ans, dfs(Ans))
        Ans.pop()
    return ans

n, m, q = map(int, readline().split())
A,B,C,D = [0]*q, [0]*q, [0]*q, [0]*q
for i in range(q):
    a,b,C[i],D[i] = map(int, readline().split())
    A[i] = a-1
    B[i] = b-1

print(dfs([]))
n,m,x,y = map(int,input().split())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
if x<y-1 and max(x)<min(y)-1:
    print("No War")
else:
    print("War")


### FIXED CODE ###

n,m,x,y = map(int,input().split())
xx = list(map(int,input().split()))
yy = list(map(int,input().split()))
if x<y and max(xx)<min(yy) and x<min(yy) and max(xx)<y:
    print("No War")
else:
    print("War")
N,M = [int(x) for x in input().split()]
map = [[0 for j in range(N+1)] for i in range(N+1)]
li_e = []
dp = [0]*(M+1)

def dfs(v,li_gr,flg):
    if(not flg[v]):
        flg[v] = True
        li_gr.append(v)
        for u,exist in enumerate(map[v]):
            if(exist == 1 and not flg[u]):
                dfs(u,li_gr,flg)

for i in range(M):
    A,B = [int(x) for x in input().split()]
    map[A][B] = 1
    map[B][A] = 1
    li_e.append((A,B))
dp[0] = [x for x in range(1,N+1)]

for i in range(M):
    flg = [True]*(N+1)
    dp[i+1] = dp[i]
    A = li_e[i][0]
    B = li_e[i][1]
    map[A][B] = 0
    map[B][A] = 0
    for n,p in enumerate(li_gr):
        if(A in p):
            for q in p:
                flg[q] = False
            dp[i+1].pop(n)
    li = []
    li.append([])
    dfs(A,li[0],flg)
    if(not flg[B]):
        li.append([])
        dfs(B,li[1],flg)
    dp[i+1].append(li)
    ans = 0
    grps = len(dp[i+1])
    for p in range(grps):
        for q in range(p+1,grps):
            ans += len(dp[i+1][p])*len(dp[i+1][q])
    print(ans)


### FIXED CODE ###

import sys
#sys.setrecursionlimit(1000000)

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

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

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

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

N,M = [int(x) for x in input().split()]
A = [0]*M
B = [0]*M
ans = [0]*M
for i in range(M):
    A[i],B[i] = [int(x) for x in input().split()]
ans[M-1] = int(N*(N-1)/2)
uni = UnionFind(N)
for i in range(M-1,0,-1):
    ans[i-1]=ans[i]
    if(not uni.same(A[i]-1,B[i]-1)):
        ans[i-1]-=uni.size(A[i]-1)*uni.size(B[i]-1)
        uni.unite(A[i]-1,B[i]-1)
for i in ans:
    print(i)
import sys
from functools import lru_cache

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER


@lru_cache(maxsize=32)
def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

@lru_cache(maxsize=None)
def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3:
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return (3 * (dp(i + 1, 3) % DEVIDER)) % DEVIDER
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            pre = (3 * (dp(i + 1, j) % DEVIDER)) % DEVIDER
            lat = dp(i + 1, j + 1)
            return (pre + lat) % DEVIDER
        if check(S[i], j):
            return (dp(i + 1, j) + dp( i + 1, j + 1)) % DEVIDER
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)





### FIXED CODE ###

import sys

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache = [[0 for _ in range(4)] for _ in range(len(S) + 1)]
cache[0][0] = 1


def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False


for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            cache[i + 1][j] += 3 * cache[i][j]
        else:
            cache[i + 1][j] += cache[i][j]
        if j > 0:
            if check(S[i], j-1) or S[i] == '?':
                cache[i+1][j] += cache[i][j - 1]
        cache[i+1][j] %= DEVIDER

print(cache[len(S)][3])
usr_input = input()
lst = usr_input.split()

a = int(lst[0])
b = int(lst[1])
c = int(lst[2])

devider_a=[]
devider_b=[]
for i in range(1,a,1):
    if a%i == 0:
        devider_a.append(i)

for i in range(1,b,1):
    if b % i == 0:
        devider_b.append(i)

common_devider = []
for element in devider_a:
    for value in devider_b:
        if element==value:
            common_devider.append(value)

print(common_devider[c-1])


### FIXED CODE ###

usr_input = input()
lst = usr_input.split()

a = int(lst[0])
b = int(lst[1])
c = int(lst[2])

if b//a < c:
    print(b//a)
else:
    print(c)
N, X, M = map(int, input().split())

ans = X
x = X

C = [0, x]
Xd = [-1] * (M+1)
Xd[x] = 0
Xl = [x]

for i in range(1, N):
    x = x**2 % M

    if Xd[x] > -1:
        break
    Xd[x] = i
    Xl.append(x)
    ans += x
    C.append(ans)

# print(Xl)
# print(C)
# print(Xd[x], i)
loop_len = i - Xd[x]
# print(loop_len)
if loop_len > 0:
    #S = C[i] - C[Xd[x]]
    # print(S)
    loop_num = (N - i) // loop_len
    # print(loop_num)
    #ans += loop_num * S
    m = N - loop_num * loop_len - i
    # print(ans)
    # print(m)
    ans += C[Xd[x]+m] - C[Xd[x]]

# print(S)

print(ans)

### FIXED CODE ###

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

ans = X
x = X

C = [0, x]
Xd = [-1] * (M+1)
Xd[x] = 0
i = 1

for i in range(1, N):
    x = x**2 % M

    if Xd[x] > -1:
        break
    Xd[x] = i
    ans += x
    C.append(ans)

loop_len = i - Xd[x]
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    loop_num = (N - i) // loop_len
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    ans += C[Xd[x]+m] - C[Xd[x]]

print(ans)
import sys
N,*W = map(str,open().read().split())
N = int(N)
for i in range(N-1):
    if list(W[i])[-1] != list(W[i+1])[0]:
        print("No")
        sys.exit()
print("Yes")

### FIXED CODE ###

import sys
N,*W = map(str,open(0).read().split())
N = int(N)
for i in range(N-1):
    if list(W[i])[-1] != list(W[i+1])[0]:
        print("No")
        sys.exit()
if len(W) != len(set(W)):
    print("No")
    sys.exit()
print("Yes")
n = int(input())


days = [] 
for _ in range(n):
  temp = list(map(int,input().split()))
  days.append(temp)
  
dp = [0]*n

for i in range(3):
  dp[i]= days[0][i]
#print(dp) 
for cur_day in range(1,n):
  m = [0]*n
  for i in range(3):
    for j in range(3):
      if i!=j:
        m[j] = max(m[j],dp[j]+days[cur_day][i])
  dp = m
#  print(dp)
  
print(max(dp))
  

### FIXED CODE ###

n = int(input())

days=[]
dp = [0]*3
for _ in range(n):
  a = list(map(int,input().split()))
  days.append(a)

for i in range(3):
  dp[i]=days[0][i]
  
#rint(dp)
for cday in range(1,n):
  pday = cday-1
  t = [0]*3
  for i in range(3):
    max_val = dp[i]
    for j in range(3):
      if i!=j:
        cur_val = dp[j] + days[cday][i]
        if cur_val>max_val:
          max_val=cur_val
    
    t[i] = max_val
  dp=t
  #rint(dp)
  	
print(max(dp))