Harryxun/stf_run huggingface dataset:
import math

def regular(i1, i2, res1, res2):
    return ((i1 % 2 == i2 % 2) and not (res1 == res2)) or (not (i1 % 2 == i2 % 2) and (res1 == res2))

def search(range_list, result_list):

    print(range_list)
    next_range_list = []
    next_result_list = []

    for r in zip(range_list, result_list):
        rng = r[0]
        result = r[1]
        half = rng[0] + math.floor((rng[1] - rng[0])/2)

        res = input()

        if res == 'Vacant':
            return
        else:
            if rng[0] == rng[1]:
                return

            if regular(result[0], half, result[1], res):
                next_range_list.append((rng[0], half - 1))
                next_range_list.append((half + 1, rng[1]))
                next_result_list.append((half, res))
                next_result_list.append((half, res))

            else:
                search([(rng[0], half - 1)], [(half, res)])
                return


    search(next_range_list, next_result_list)

def main():
    N = int(input())

    print(0)
    res1 = input()
    half = math.floor(N/2)
    print(half)
    res2 = input()

    if res1 == 'Vacant' or res2 == 'Vacant':
        return

    range_list = []
    result_list = []

    if regular(0, half, res1, res2):
        if 1 <= half-1:
            range_list.append((1, half-1))
            result_list.append(0, res1)
        if half+1 <= N-1:
            range_list.append((half + 1, N-1))
            result_list.append(half, res2)
    else:
        if 1 <= half - 1:
            range_list = [(1, half-1)]
            result_list = [(0, res1)]
        else:
            range_list = [(half+1, N-1)]
            result_list = [(half, res2)]

    search(range_list, result_list)

main()


### FIXED CODE ###


import math
import sys

def isBetween(i1, i2, res1, res2):
    return (i1 % 2 == i2 % 2) != (res1 == res2)

def search(s_range, isLeft, result):
    half = s_range[0] + math.floor((s_range[1] - s_range[0])/2)
    print(half)
    res = input()

    if res == 'Vacant':
        return

    if isLeft:
        if isBetween(s_range[0]-1, half, result, res):
            search((s_range[0], half-1), False, res)
        else:
            search((half+1, s_range[1]), True, res)
    else:
        if isBetween(half, s_range[1]+1, res, result):
            search((half+1, s_range[1]), True, res)
        else:
            search((s_range[0], half-1), False, res)


def main():
    N = int(input())

    print(0)
    res = input()

    s_range = (1, N-1)
    search(s_range, True, res)

main()
n,k=map(int, input().split())
xlist=list(map(int, input().split()))
num0=0
nump=0
numm=0
for i in xlist:
  if i>0:
    nump+=1
  elif i<0:
    numm+=1
  else:
    num0+=1
listp=[0]*(nump+1)
listm=[0]*(numm+1)
for i in range(1,nump+1):
  listp[i]=xlist[numm+num0+i-1]
for i in range(1,numm+1):
  listm[i]=-xlist[numm-i]
cnt=k-num0
ans=10**30
for i in range(cnt):
  if i<=numm and cnt-i<=nump:
    ans=min(ans,listm[i]+listp[cnt-i]+min(listm[i],listp[cnt-i]))
if numm==0 and nump==0:
  ans=0
elif numm==0:
  ans=listp[cnt+1]
elif nump==0:
  ans=listm[cnt+1]
print(ans)

### FIXED CODE ###

n,k=map(int, input().split())
xlist=list(map(int, input().split()))
ans=10**20
for i in range(n-k+1):
  ans=min(abs(xlist[i]-xlist[i+k-1])+min(abs(xlist[i]),abs(xlist[i+k-1])),ans)
print(ans)
n = input()
k = input()
x = input()
y = input()
sum = 0
sum += k * x
sum += (n-k) * y
print(sum)


### FIXED CODE ###

n = int(input())
k = int(input())
x = int(input())
y = int(input())
sum = 0
if n >= k:
    sum += k * x
    sum += (n-k) * y
else:
    sum += n*x
print(sum)
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

MODN = (10 ** 9) + 7

INF = 10 ** 10

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


# K個の青ボールとN-K個の赤ボール
# 同じ色のボールは区別可能
N, K = [int(x) for x in stdin.readline().rstrip().split()]

blue_num = K
red_num = N - K

red_p = permutations_count(red_num, 1)
pos_cand_num = red_p + 1

for i in range(1, K+1):
    ans = combinations_count(pos_cand_num, i) % MODN * combinations_count(K-1, i-1) % MODN
    print(ans) 

### FIXED CODE ###

from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

MOD = (10 ** 9) + 7

INF = 10 ** 10

MAX = 510000

def com_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


def com(n, k):
    if n < k:
        return 0
    if (n < 0) or (k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


if __name__ == "__main__":
    # K個の青ボールとN-K個の赤ボール
    # 同じ色のボールは区別可能
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX

    com_init()

    for i in range(1, K+1):
        ans = com(N-K+1, i) * com(K-1, i-1) % MOD
        print(ans)
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[x] = y # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    # if same(c - 1, d - 1):
    #     blocks[c - 1].add(d - 1)
    #     blocks[d - 1].add(c - 1)
    blocks[c - 1].add(d - 1)
    blocks[d - 1].add(c - 1)

for i in range(n):
    candidates[i] = sizes[root(i)] - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if y < x:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)
s = input()
K = int(input())
substring = []
for i in range(len(s) + 1):
	for j in range(i + 1, len(s) + 1):
		substring.append(s[i:j])
substring = list(set(substring))
substring.sort()
if len(substring) <= 1:
	print(s)
else:
	print(substring[K - 1])

### FIXED CODE ###

s = input()
K = int(input())
substr = set()
for i in range(len(s)):
    for j in range(i+1, i+K+1):
        substr.add(s[i:j])
print(sorted(substr)[K-1])
for i in range(1,10):
   for j in range(1,10):
      ans = i * j
      print('%dx%d=%d' % (i,j,k))

### FIXED CODE ###

for i in range(1,10):
    for j in range(1,10):
        ans = i * j
        print('%dx%d=%d' % (i,j,ans))
import bisect
n,k=map(int,input().split())
mod=10**9+7;ans=0
a=list(map(int,input().split()))
c=sorted(a)
d=[0]*n
e=[0]*n
for i in range(n):
  d[i]=bisect.bisectleft(c,a[i])
for i in range(n):
  cnt=0
  for j in range(i,n):
    if a[i]>a[j]:
      cnt+=1
  e[i]=cnt
st=sum(e)*k%mod
ad=sum(d)%mod
print((st+(ad*(k-1)*k//2)%mod)%mod)


### FIXED CODE ###

import bisect
n,k=map(int,input().split())
mod=10**9+7
a=list(map(int,input().split()))
c=sorted(a)
d=[0]*n
e=[0]*n
for i in range(n):
  d[i]=bisect.bisect_left(c,a[i])
for i in range(n):
  cnt=0
  for j in range(i,n):
    if a[i]>a[j]:
      cnt+=1
  e[i]=cnt
st=sum(e)*k%mod
ad=sum(d)%mod
print((st+(ad*(k-1)*k//2)%mod)%mod)
a,b = int(input().split(" "))
print("Even" (a*b)%2==0 else "Odd")

### FIXED CODE ###

a,b = map(int,input().split(" "))
print("Even" if (a*b)%2==0 else "Odd")
x = int(input())
li,p,ans = [],1,0

for b in range(2,int(x**0.5//1)+1):
    while b**p<=x:
        ans = max(ans,b**p)
        p += 1
        li.append(b**(p-1))
        if b**p>x:
            p = 1
            break
        
print(max(li))

### FIXED CODE ###

x = int(input())
li,p,ans = [],1,0

for b in range(2,int(x**0.5//1)+1):
    while b**p<=x:
        ans = max(ans,b**p)
        p += 1
        li.append(b**(p-1))
        if b**p>x:
            p = 1
            break
if x <= 3:
    print(x)
else:
    print(max(li))
from collections import Counter
N,M = map(int,input().split())
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
mod = 10**9 + 7
num = prime_factorize(M)
numc = Counter(num)
nums = list(numc.values())
H = [0 for i in range(max(nums)+1)]
for i in set(nums):
    H[i] = comb(N+i-1,i,mod)
ans = 1
for i in nums:
    count = H[i]
    ans = (ans*count)%mod
print(ans)

### FIXED CODE ###

from collections import Counter
N,M = map(int,input().split())
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
mod = 10**9 + 7
num = prime_factorize(M)
numc = Counter(num)
nums = list(numc.values())
if nums:
    H = [0 for i in range(max(nums)+1)]
    for i in set(nums):
        H[i] = comb(N+i-1,i,mod)
    ans = 1
    for i in nums:
        count = H[i]
        ans = (ans*count)%mod
    print(ans)
else:
    print(1)
L, N = (int(i) for i in input().split())
X = [int(input()) for _ in range(N)]
X.insert(0, 0)

X_c = [L - i for i in X]

def f(L, N, X, p, l, r, d_r):
    w = 0
    for _ in range(N - (l + r)):
        if d_r:  # L
            l += 1
            w += X[l] - p
            p = X[l]
            d_r = False
        else:  # R
            r += 1
            w += L - X[-r] + p
            p = X[-r] - L
            d_r = True
    return w

len_l = [X[i] + f(L, N, X, X[i], i, 0, True) for i in range(1, N)]
len_r = [X_c[-i] + f(L, N, X, X[-i] - L, 0, i, False) for i in range(1, N)]
max_l = max(len_l)
max_r = max(len_r)
print(max(max_l, max_r))


### FIXED CODE ###

import math

L, N = (int(i) for i in input().split())
X = [int(input()) for _ in range(N)]
X.insert(0, 0)

X_r = [L - i for i in reversed(X)]
X_r.insert(0, 0)
X_r.pop()

def lsum(l):
    s = 0
    for i in l:
        s += i
        yield s

X_sum = list(lsum(X))
X_r_sum = list(lsum(X_r))

def f_l(p, n):
    N_tmp = N - n
    a = N_tmp // 2
    if N_tmp == 0:
        return 0
    elif N_tmp % 2 == 0:
        return 2 * X_sum[a] + X_r_sum[a + n] + X_r_sum[a + n - 1] - 2 * X_r_sum[n] + p
    else:
        return X_sum[a+1] + X_sum[a] + 2 * X_r_sum[a + n] - 2 * X_r_sum[n] + p


def f_r(p, n):
    N_tmp = N - n
    a = N_tmp // 2
    if N_tmp == 0:
        return 0
    elif N_tmp % 2 == 0:
        return 2 * X_r_sum[a] + X_sum[a + n] + X_sum[a + n - 1] - 2 * X_sum[n] + p
    else:
        return X_r_sum[a+1] + X_r_sum[a] + 2 * X_sum[a + n] - 2 * X_sum[n] + p

max_l = max(X[i] + f_r(X[i], i) for i in range(1, N+1))
max_r = max(X_r[i] + f_l(X_r[i], i) for i in range(1, N+1))

print(max(max_l, max_r))
a=[1,3,5,7,8,10,12]
b=[4,6,9,11]
ans=''
x,y=map(int,input().split(' '))
ans='Yes' if x==y
for c in (a,b):
    ans='Yes' if x in c and y in c
if ans=='': ans='No'
print(ans)


### FIXED CODE ###

a=[1,3,5,7,8,10,12]
b=[4,6,9,11]
ans=''
x,y=map(int,input().split(' '))
if x==y: ans='Yes'
else:
    for c in [a,b]:
        if (x in c)*(y in c):
            ans='Yes'
            break
if ans=='': ans='No'
print(ans)
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
c = float("inf")
for i in range(n-1):
  c = min(c, a[i+1]-a[i])
  if c == 1:
    break
if k > a[-1]:
  print("IMPOSSIBLE")
else:
  kr = k%c
  for i in a:
    if kr == i%c:
      print("POSSIBLE")
      exit()
  print("IMPOSSIBLE")

### FIXED CODE ###

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
c = float("inf")
for i in range(n-1):
  if a[i] == a[i+1]:
    continue
  else:
    c = min(c, a[i+1]-a[i])
    if c == 1:
      break
if k > a[-1]:
  print("IMPOSSIBLE")
else:
  kr = k%c
  for i in a:
    if kr == i%c:
      print("POSSIBLE")
      exit()
  print("IMPOSSIBLE")
def main():
    N = input()
    N = int(N)

    k = 1
    s = []
    #lst = list(range(1,N+1))
    primes = prime(N)
    num = len(primes)

    # N=1
    lst = [0] * N
    if N ==1:
        print(1)

    # N>=2
    for i in range(2,N+1):
        b =[]
        b = bunkai(i)
        for i in b:
            lst[primes.index(i)] += 1

    ans = 1
    for i in lst:
        if i is not 0:
            ans = ans * (i+1)
    print(ans/1000000007)


def prime(n):
    primes = []
    for i in range(2,n):
        flag = True
        for j in range(2,i):
            if i%j == 0:
                flag = False
        if flag:
            primes.append(i)
    return primes

def bunkai(i):
    bunkai =[]
    s =0
    while s ==0:
        for j in range(2,i+1):
            if i % j ==0:
                bunkai.append(j)
                i = int(i/j)
                if i ==1:
                   s=1
                break
    return bunkai

if __name__ == "__main__":
        main()


### FIXED CODE ###

def main():
    N = input()
    N = int(N)

    k = 1
    s = []
    #lst = list(range(1,N+1))
    primes = prime(N+1)
    num = len(primes)

    # N=1
    lst = [0] * N
    if N ==1:
        print(1)
        exit()

    # N>=2
    for i in range(2,N+1):
        b =[]
        b = bunkai(i)
        for i in b:
            lst[primes.index(i)] += 1

    ans = 1
    for i in lst:
        if i is not 0:
            ans = ans * (i+1)
    print(ans%1000000007)


def prime(n):
    primes = []
    for i in range(2,n):
        flag = True
        for j in range(2,i):
            if i%j == 0:
                flag = False
        if flag:
            primes.append(i)
    return primes

def bunkai(i):
    bunkai =[]
    s =0
    while s ==0:
        for j in range(2,i+1):
            if i % j ==0:
                bunkai.append(j)
                i = int(i/j)
                if i ==1:
                   s=1
                break
    return bunkai

if __name__ == "__main__":
        main()
N = int(input())
P = [int(input().split())]
Q = [int(input().split())]
 
data = [i+1 for i in range(N)]
 
def listExcludedIndices(data, indices=[]):
  return [x for i, x in enumerate(data) if i not in indices]
 
def count(res,p):
    count = 0
    for i in range(len(res)):
        count +=1
        if res[i] == p:
            break
    return count
result = []
for i in range(len(data)):
  for j in range(len(data)-1):
    for k in range(len(data)-2):
      jData = listExcludedIndices(data, [i])
      kData = listExcludedIndices(jData, [j])
      result.append([data[i], jData[j], kData[k]])
print(abs(count(result,P) - count(result,Q)))

### FIXED CODE ###

N = int(input())
P = tuple(int(x) for x in input().split())
Q = tuple(int(x) for x in input().split())

import itertools
L = list(itertools.permutations(list(range(1,N+1))))
print(abs(L.index(Q) - L.index(P)))
a=list()
b=list()
a="R", "U","D"
b="L", "U", "D"
s=input()
count=0
ans=True
for i in s:
    if count%2==0:
        if i not in a:
            ans=False
    if count%2!=0:
        if i not in b:
            ans=False
    count+=1

if ans==True:
    print('Yes')
else:
    print('No')
            

### FIXED CODE ###

a=list()
b=list()
a="R", "U","D"
b="L", "U", "D"
s=input()
count=0
ans=True
for i in s:
    if count%2==0:
        if i not in a:
            ans=False
    if count%2!=0:
        if i not in b:
            ans=False
    count+=1

if ans==True:
    print('Yes')
else:
    print('No')
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
import sys

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]
rcvs = np.array(rcvs, dtype=np.int64)

@njit(i8(i8[:,:]), cache=True)
def main(rcvs):
    rewards = np.zeros((R, C), dtype=np.int64)
    
    for i in range(len(rcvs)):
        rewards[rcvs[i][0]-1][rcvs[i][1]-1] = rcvs[i][2]
    
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1][j+1][0] = max(dp[i][j+1])
            dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
            
            for k in range(4): # move downside without selecting
                dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
            if reward > 0:
                for k in range(3):
                    dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
    return max(dp[-1][-1])

print(main(rcvs))

### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
import sys

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]
rcvs = np.array(rcvs, dtype=np.int64)

@njit(i8(i8[:,:]), cache=True)
def main(rcvs):
    rewards = np.zeros((R, C), dtype=np.int64)
    
    for i in range(len(rcvs)):
        rewards[rcvs[i][0]-1][rcvs[i][1]-1] = rcvs[i][2]
    
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1][j+1][0] = max(dp[i][j+1])
            dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
            
            for k in range(4): # move downside without selecting
                dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
            if reward > 0:
                for k in range(3):
                    dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
    return max(dp[-1][-1])

print(main(rcvs))
S = input()
l = len(S)
A,B,C,q = [0]*l,[0]*l,[0]*l,[0]*l
inf = 1000000007
for i in range(l):
    if S[i] == 'A':
        A[i] = 1
    elif S[i] == 'B':
        B[i] = 1
    elif S[i] == 'C':
        C[i] = 1
    else:
        q[i] = 1
    A[]

for i in range(l-1):
    A[i+1] += A[i]
    B[i+1] += B[i]
    C[i+1] += C[i]
    q[i+1] += q[i]

ans = 0
for i in range(1,l-1):
    if S[i] == 'B':
        ans += (A[i-1]) * (C[-1]-C[i]) * (3**q[-1])%inf
        ans %= inf
        if q[-1] >= 1:
            ans += (q[i-1]) * (C[-1] - C[i]) * (3**(q[-1]-1)%inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-1)%inf)
            ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-2)%inf)
            ans %= inf

    elif S[i] == '?':
        ans += (A[i-1]) * (C[-1]-C[i]) * (3**(q[-1]-1)%inf)
        ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (C[-1] - C[i]) * (3**(q[-1]-2)%inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-2)%inf)
            ans %= inf
        if q[-1] >= 3:
            ans += (q[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-3)%inf)
            ans %= inf

print(ans%inf)


 

### FIXED CODE ###

S = input()
l = len(S)
A,B,C,q = [0]*l,[0]*l,[0]*l,[0]*l
inf = 1000000007
for i in range(l):
    if S[i] == 'A':
        A[i] = 1
    elif S[i] == 'B':
        B[i] = 1
    elif S[i] == 'C':
        C[i] = 1
    else:
        q[i] = 1

for i in range(l-1):
    A[i+1] += A[i]
    B[i+1] += B[i]
    C[i+1] += C[i]
    q[i+1] += q[i]

ans = 0
for i in range(1,l-1):
    if S[i] == 'B':
        ans += (A[i-1]) * (C[-1]-C[i]) * pow(3,q[-1],inf)
        ans %= inf
        if q[-1] >= 1:
            ans += (q[i-1]) * (C[-1] - C[i]) * pow(3,q[-1]-1,inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-1,inf)
            ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-2,inf)
            ans %= inf

    elif S[i] == '?':
        ans += (A[i-1]) * (C[-1]-C[i]) * pow(3,q[-1]-1,inf)
        ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (C[-1] - C[i]) * pow(3,q[-1]-2,inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-2,inf)
            ans %= inf
        if q[-1] >= 3:
            ans += (q[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-3,inf)
            ans %= inf

print(ans%inf)
n=int(input())
A=[int,input().split()]

dp=list(range(0,n))
dp[0]=0
dp[1]=abs(A[1]-A[0])
for i in range(n-2):
  temp1=dp[i]+abs(A[i+2]-A[i])
  temp2=dp[i+1]+abs(A[i+2]-A[i+1])
  dp[i+2]=min(temp1,temp2)

print(dp[n-1])

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
 
dp=list(range(0,n))
dp[0]=0
dp[1]=abs(A[1]-A[0])
for i in range(n-2):
  temp1=dp[i]+abs(A[i+2]-A[i])
  temp2=dp[i+1]+abs(A[i+2]-A[i+1])
  dp[i+2]=min(temp1,temp2)
 
print(dp[n-1])
n=int(input())
dat = list(map(int, input().split()))
dan = []
for e in dat:
    e = str(bin(e))
    e=e[2:]
       
for e in dat:
      dan.append(len(e))
                

         
           




### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()