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

S = input()
before_number = ""
counter = 0
ans = 0

while 1 == 1:
    counter1 = S.count("01")
    S = S.replace("01", "")
    ans += counter1
    counter2 = S.count("10")
    S = S.replace("10", "")
    ans += counter2
    if counter1 == 0 and counter2 == 0:
        break

print(ans*2)


### FIXED CODE ###

S = input()
counter0 = int(S.count("0"))
counter1 = int(S.count("1"))
print(min(counter0, counter1)*2)
### BUGGY CODE ###

def resolve():
    t = input()

    ans = ''
    for s in t:
        if s == '?':
            ans += 'D'
        else:
            ans += s

    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    t = input()

    print(t.replace('?', 'D'))
resolve()
### BUGGY CODE ###

from math import factorial

iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    iS = int(iM ** 0.5) + 1
    aRet = []
    for i in range(2,iS + 1):
        iCounter = 0
        while iM % i == 0:
            iM = iM / i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        if iM == 1 : break
    if 1 < iM  : aRet.append(1)
    return aRet

aP = fPrimeCounter(iM)
iRet = 1
for i in aP:
    iRet *= (factorial(i+iN-1)  // (factorial(iN-1) * factorial(i)) )% iD
iRet %= iD
print(iRet)



### FIXED CODE ###

iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    i = 2
    iS = int(iM ** 0.5) + 1
    aRet = []
    while i < iS or iM != 1:
        iCounter = 0
        while iM % i == 0:
            iM = iM // i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        i += 1

    return aRet

#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
if aP == [] :
    print (1)
else:
    iMax = max(aP) + iN - 1
    aM = [1] * (iMax + 1)
    #階乗 iD を法とした
    for i in range(1,iMax + 1):
        aM[i] = aM[i-1] * i  % iD
    aInvM = [1]* (iMax + 1)
    aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
    #階乗の逆元 iD を法とした
    for i in range(iMax,0,-1):
        aInvM[i-1] = aInvM[i]*i % iD

    iRet = 1
    for i in aP:
        # i + iN -1  C  iN -1
        iRet *= aM[i+iN-1] * aInvM[iN-1] * aInvM[i] % iD
    iRet %= iD
    print(iRet)
### BUGGY CODE ###

N, P = map(int, raw_input().split())
i = 2
res = 1
while i ** N <= P:
    if P % (i ** N) == 0:
        res = i
    i += 1
print res


### FIXED CODE ###

N, P = map(int, raw_input().split())
max_N = 40
if N == 1:
    print P
elif N >= max_N:
    print 1
else:
    res = 1
    i = 2
    while i ** N <= P:
        if P % (i ** N) == 0:
            res = i
        i += 1
    print res
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

n, m = MAP()
for i in range(n, m + 1):
    if m % i == 0:
        print(m // i)
        exit()

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

n, m = MAP()
a = make_divisors(m)
for i in a:
    if i >= n:
        print(m // i)
        exit()
### BUGGY CODE ###

from collections import Counter


def main():
    N = int(input()) # 5人
    An = list(map(int, input().split(' '))) # A2, A3,...
    
    # N = 10
    # An = [1,1, 1, 1, 1, 1, 1, 1, 1]
    
    start_index = 0
    
    for n in range(1, N+1):
        an = Counter(An[start_index:])
        start_index = an[n]
        print(start_index)
            


    
main()


### FIXED CODE ###

from collections import Counter


def main():
    N = int(input()) # 5人
    An = list(map(int, input().split(' '))) # A2, A3,...
    
    # N = 10
    # An = [1,1, 1, 1, 1, 1, 1, 1, 1]
    
    # out = [0] *
    
    an = Counter(An)
    for n in range(1, N+1):  
        print(an[n])
            


    
main()
### BUGGY CODE ###

n = int(input())
S = []
for i in range(n):
    tmp = list(input())
    tmp.sort()
    S.append(tmp)
count = 0
for j in range(len(S)):
    for k in range(j+1,len(S)):
        if S[j] == S[k]:
            count+=1
print(count)

### FIXED CODE ###

import collections
n = int(input())
s = collections.Counter(["".join(sorted(input())) for _ in range(n)]).most_common()
#print(s)
cnt = 0
for i in s:
    for j in range(1, i[1]):
        cnt += j
print(cnt)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
dp = [0] * (N + 1)
for i in range(N, 0, -1):
  #print(i)
  if i > N // 2:
    dp[i] = a[i - 1]
  else:
    j = 2
    while i * j <= N:
      dp[i] = dp[i] ^ dp[i * j]
      j += 1
    dp[i] = dp[i] ^ a[i - 1]
M = 0
res2 = ""
#print(dp)
for i, v in enumerate(dp):
  if v == 1:
    M += 1
    res2 += str(i) + " "
print(M)
print(res2)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
res = [0] + a[:]
for i in range(N, 0, -1):
  res[i] = sum(res[i : : i]) % 2 
print(sum(res))
print(*[i for i in range(N + 1) if res[i]])
### BUGGY CODE ###

import math
N = int(input())


# if a * a + b * b + c * c + ab + bc + ac == i:
    
count = 0

for i in range(1, N + 1):
    if i < 6:
        print(0)
        continue
    sqrt = int(math.sqrt(i))
    for x in range(1, sqrt + 1):
        if x**2 > i:
            break
        for y in range(1, sqrt + 1):
            if x * x + y*y + x*y > i:
                break
            for z in range(1, sqrt + 1):
                 if (x + y + z) ** 2 -x*y -y*z -x*z == i:
                     count += 1
    print(count)
    count = 0

### FIXED CODE ###

import math
N = int(input())

ans = [0 for _ in range(10050)]


for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            a = x**2+y**2+z**2+x*y+y*z+z*x
            if  a < 10050:
                ans[a] +=1

for i in range(N):
    print(ans[i+1])
### BUGGY CODE ###

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp
sample_input = list(range(3))
sample_input[0] = '''7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5'''
sample_input[1] = '''9
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5
deleteFirst
deleteLast'''
sample_input[2] = '''8
insert 1000000000
insert 999999999
deleteLast
insert 1234566890
insert 5
deleteFirst
insert 7
delete 5'''
give_sample_input = None
if give_sample_input is not None:
    sample_input_list = sample_input[give_sample_input].split('\n')
    def input():
        return sample_input_list.pop(0)
        
# main
class DoublyLinkedList():
    
    def __init__(self, a_data = []):
        self.data = a_data
    
    def insert(self, x):
        self.data.insert(0, x)
    
    def delete(self, x):
        try:
            self.data.remove(x)
        except ValueError:
            return
    
    def delete_first(self):
        self.data.pop(0)
    
    def delete_last(self):
        self.data.pop()

    def to_str(self):
        output = ''
        for x in self.data:
            output += str(x) + ' '
        output = output.rstrip()
        return output

num_of_command = int(input())
doublely_list = DoublyLinkedList()
for n in range(num_of_command):
    str_command = input()
    if str_command == 'deleteFirst':
        doublely_list.delete_first()
        continue
    elif str_command == 'deleteLast':
        doublely_list.delete_last()
        continue
    command_name = str_command.split()[0]
    command_obj = int(str_command.split()[1])
    if command_name == 'insert':
        doublely_list.insert(command_obj)
    elif command_name == 'delete':
        doublely_list.delete(command_obj)

print(doublely_list.to_str())

### FIXED CODE ###

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp
sample_input = list(range(3))
sample_input[0] = '''7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5'''
sample_input[1] = '''9
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5
deleteFirst
deleteLast'''
sample_input[2] = '''8
insert 1000000000
insert 999999999
deleteLast
insert 1234566890
insert 5
deleteFirst
insert 7
delete 5'''
give_sample_input = None
if give_sample_input is not None:
    sample_input_list = sample_input[give_sample_input].split('\n')
    def input():
        return sample_input_list.pop(0)
        
# main
from collections import deque

num_of_command = int(input())
doubly_list = deque()
for n in range(num_of_command):
    str_command = input()
    if str_command == 'deleteFirst':
        doubly_list.popleft()
        continue
    elif str_command == 'deleteLast':
        doubly_list.pop()
        continue
    command_name = str_command.split()[0]
    command_obj = int(str_command.split()[1])
    if command_name == 'insert':
        doubly_list.appendleft(command_obj)
    elif command_name == 'delete':
        try:
            doubly_list.remove(command_obj)
        except ValueError:
            continue

output = ''
for item in doubly_list:
    output += str(item) + ' '
output = output.rstrip()
print(output)
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
from __pypy__ import builders
readline = sys.stdin.readline
N, Q = map(int, readline().split())
U = [0]*N
qs = []
for i in range(N):
    s, t, x = map(int, readline().split())
    qs.append((s-x, x, i, 1))
    qs.append((t-x, x, i, 0))
qs.sort()

b = builders.StringBuilder(Q)
que = []
j = 0
for i in range(Q):
    d = int(readline())
    while j < 2*N and qs[j][0] <= d:
        _, x, i, m = qs[j]
        if m:
            heappush(que, (x, i))
        else:
            U[i] = 1
        j += 1
    while que and U[que[0][1]]:
        heappop(que)
    if que:
        b.append("%d\n" % que[0][0])
    else:
        b.append("-1\n")
sys.stdout.write(b.build())

### FIXED CODE ###

from heapq import heappush, heappop
import sys
from __pypy__ import builders
readline = sys.stdin.readline
N, Q = map(int, readline().split())
qs = [0]*N
for i in range(N):
    s, t, x = map(int, readline().split())
    qs[i] = (s-x, t-x, x)
qs.sort()

b = builders.StringBuilder(Q)
que = []
D = [int(readline()) for i in range(Q)]
j = 0
for d in D:
    while j < N and qs[j][0] <= d:
        s, t, x = qs[j]
        heappush(que, (x, t))
        j += 1
    while que and que[0][1] <= d:
        heappop(que)
    if que:
        b.append("%d\n" % que[0][0])
    else:
        b.append("-1\n")
sys.stdout.write(b.build())
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [0] * Q
for i in range(Q):
    A[i] = int(input())

initial_point = [K] * N
import numpy as np
initial_point = np.array(initial_point)

for i in range(Q):
    initial_point -= 1
    initial_point[(A[i]-1)] += 1

for i in range(N):
    if initial_point[i] > 0 :
        print("Yes")
    else:
        print("No")   

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [0] * Q
for i in range(Q):
    A[i] = int(input())

initial_point = [(K-Q)]*N

for i in range(Q):
    initial_point[(A[i]-1)] += 1

for i in range(N):
    if initial_point[i] > 0 :
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n, m = (int(i) for i in input().split()) 
l = [[int(i) for i in input().split()] for i in range(m)]  

ans = 0
for i in range(1, n+1):
  c = 0
  for ll in l:
    if i>=ll[0] and i<=ll[1]:
      c += 1
    else:
      break
  if c == m:
    ans += 1
    
print(ans)

### FIXED CODE ###

n, m = (int(i) for i in input().split()) 
l = [[int(i) for i in input().split()] for i in range(m)]

import numpy as np
nl = np.array(l)
mrange = l[(nl[:, 1] - nl[:, 0]).argmin()]

def judge(l):
  a = l[1]<mrange[0]
  b = l[0]<mrange[0] and l[1]>=mrange[0] and l[1]<=mrange[1]
  c = l[0]>=mrange[0] and l[1]<=mrange[1]
  d = l[0]>=mrange[0] and l[0]<=mrange[1] and l[1]>mrange[1]
  e = l[0]>mrange[1]
  return a, b, c, d, e

for ll in l:
  a, b, c, d, e = judge(ll)
  if a | e:
    mrange = [1, 0]
    break
  elif b:
    mrange = [mrange[0], ll[1]]
  elif c:
    mrange = ll # これは出現することがないはず
  elif d:
    mrange = [ll[0], mrange[1]]
    
print(mrange[1] - mrange[0] + 1)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd_list(nums):
    return reduce(fractions.gcd, nums)

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

ans = 0
for i in range(n):
    B = A[: i] + A[i + 1: ]
    ans = max(ans, gcd_list(B))

print(ans)

### FIXED CODE ###

from fractions import gcd

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

L, R = [0] * (n + 1), [0] * (n + 1)
for i in range(n):
    L[i + 1] = gcd(L[i], A[i])
    R[n - i - 1] = gcd(R[n - i], A[n - i - 1])
ans = 0
for i in range(n):
    ans = max(ans, gcd(L[i], R[i + 1]))

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

def rabin_karp(T, P, d):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = 1
    p = 0
    t0 = 0
    for _ in range(m - 1):
        h *= d
    for i in range(m):
        p = d * p + P[i]
        t0 = d * t0 + T[i]
    ans = []
    for s in range(n - m + 1):
        if p == t0:
            ans.append(s)
        if s < n - m:
            t0 = d * (t0 - T[s] * h) + T[s + m]
    for s in ans:
        print(s)


d = 167
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d)


### FIXED CODE ###

def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)
### BUGGY CODE ###



def YesNo(b):
    print("Yes" if b else "No")


def solve(n, v, l, ini):
    ml = n*2+1
    dp = [[False]*ml for i in range(len(l)+1)]
    for i in range(len(ini)):
        dp[0][ini[i]+n] = True
    for i in range(1, len(l)+1):
        for j in range(ml):
            if (j+l[i-1]) < ml and dp[i-1][j]:
                dp[i][j+l[i-1]] = True
            if (j-l[i-1]) >= 0 and dp[i-1][j]:
                dp[i][j-l[i-1]] = True
    return dp[len(l)][v+n]


s = input()
x, y = map(int, input().split())
si = 0
while si < len(s) and s[si] == 'F':
    si += 1

s = s[si:]
if len(s) == 0:
    YesNo(x == si and y == 0)
else:
    f = s.split('T')[1:]
    xl, yl = [], []
    for i in range(len(f)):
        if i % 2 == 0:
            yl.append(len(f[i]))
        else:
            xl.append(len(f[i]))

    if len(yl) == 0:
        yl.append(0)
    YesNo(solve(len(s), x, xl, [si]) and solve(len(s), y, yl[1:], [-yl[0], yl[0]]))


### FIXED CODE ###


def YesNo(b):
    print("Yes" if b else "No")


def solve(v, l, ini):
    ml = 8000*2+1
    dp = [[False]*ml for i in range(len(l)+1)]
    for i in range(len(ini)):
        dp[0][ini[i]+8000] = True
    for i in range(1, len(l)+1):
        for j in range(ml):
            if (j+l[i-1]) < ml and dp[i-1][j]:
                dp[i][j+l[i-1]] = True
            if (j-l[i-1]) >= 0 and dp[i-1][j]:
                dp[i][j-l[i-1]] = True
    return dp[len(l)][v+8000]


s = input()
x, y = map(int, input().split())
si = 0
while si < len(s) and s[si] == 'F':
    si += 1

s = s[si:]
if len(s) == 0:
    YesNo(x == si and y == 0)
else:
    f = s.split('T')[1:]
    xl, yl = [0], [0]
    for i in range(len(f)):
        if len(f[i]) == 0:
            continue
        if i % 2 == 0:
            yl.append(len(f[i]))
        else:
            xl.append(len(f[i]))

    YesNo(solve(x, xl, [si]) and solve(y, yl[1:], [-yl[0], yl[0]]))
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

N = int(input())
a = [0] + list(map(int, input().split()))

@functools.lru_cache(None)
def dp(i,j):
    if i == j: return 0
    if (N % 2 == 0 and (j - i) % 2 == 0) or (N % 2 == 1 and (j - i) % 2 == 1):
        return max(dp(i+1,j) + a[i], dp(i,j-1) + a[j-1])
    else:
        return min(dp(i+1,j) - a[i], dp(i,j-1) - a[j-1])

print(dp(1,N+1))

### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

N = int(input())
a = [0] + list(map(int, input().split()))

dp = [[0]*(N+5) for i in range(N+5)]

for k in range(1,N+1):
    for l in range(1,N+2-k):
        r = l + k
        if (N-k) % 2 == 0:
            dp[l][r] = max(dp[l+1][r] + a[l], dp[l][r-1] + a[r-1])
        else:
            dp[l][r] = min(dp[l + 1][r] - a[l], dp[l][r - 1] - a[r - 1])

print(dp[1][N+1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = A[0]

for n in range(1,N):
  ans = ans * A[n]

if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
if 0 in A:
  print(0)
  exit()
ans = A[0]

for n in range(1,N):
  ans = ans * A[n]
  if ans > 10**18:
    print(-1)
    exit()


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

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0 for i in range(n)]
for i in range(1, n):
    m = 10**10
    index = i-1
    num = k
    while index >= 0 and num:
        m = min(m, dp[index]+abs(h[index]-h[i]))
        index-=1
        num-=1
    dp[i] = m
print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0 for i in range(n)]
for i in range(1, n):
    m = 10**10
    index = i-1
    num = k
    while index >= 0 and num:
        m = min(m, dp[index]+abs(h[index]-h[i]))
        index-=1
        num-=1
    dp[i] = m
print(dp[n-1])
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit
import numpy as np

setrecursionlimit(10 ** 7)

n,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))
a = np.array(a,dtype=np.int64)
lamp= np.zeros(n,dtype=np.int64)
#a = np.array([(10**5)*2]*((10**5)*2))
#n = (10**5)*2

for i,j in enumerate(a):
    lamp[max(0,i-j):min(n+1,i+j+1)] += 1

if k == 1:
    print(*lamp)
    exit()

for _ in range(min(k-1,6)):
    b = np.zeros(n,dtype=np.int64)
    for i,j in enumerate(lamp):
        b[max(0,i-j):min(n+1,i+j+1)] += 1
    b[b>n] = n
    lamp = b.copy()

lamp[lamp>n] = n

print(*lamp)

### FIXED CODE ###

from itertools import accumulate
from copy import deepcopy

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*(n+1)

if k > 41:
    k = 41

for _ in range(k):
    b = [0]*(n+1)
    for i,j in enumerate(a):
        b[max(0,i-j)] += 1
        b[min(n,i+j+1)] -= 1
    a = list(accumulate(b))
    for i in range(n+1):
        if a[i] >= n:
            a[i] = n

print(*a[:-1])
### BUGGY CODE ###

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

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[0]*N,[1]*N,[1]*N,[0]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (A3[i]//3*(A1[i]*3 + A2[i])) % mod 
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (C3[i]//3*(C1[i]*3 + C2[i])) % mod
        Ans += ta*tc

print(Ans % mod)

### FIXED CODE ###

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

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = pow(3,A2[i],mod)*A1[i] + pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)
### BUGGY CODE ###

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

array=map(int,input().split())

A=[0]
for i in array:
    A.append(i)

visit=[]
visited=1
once=0
while True:
    visit.append(visited)
    once+=1
    if A[visited] in visit:
        break
    visited=A[visited]

roop=visit[visit.index(A[visited]):]
if K<once:
    print(visit[K])
else:
    order=K-once
    print(roop[order%len(roop)])

### FIXED CODE ###

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

array=map(int,input().split())

A=list(array)
A.insert(0,0)

visit=0
root=[]
visited=1
once=0
while True:
    if visit & (0b1<<visited):
        break
    root.append(visited)
    visit|=0b1<<visited
    once+=1
    visited=A[visited]

roop=root[root.index(visited):]
if K<once:
    print(root[K])
else:
    order=K-once
    print(roop[order%len(roop)])