Harryxun/stf_run huggingface dataset:
def plus(number_list):
    return sum([int(num) for num in number_list])


def minus(number_list):
    numbers = [int(num) for num in number_list]
    return numbers[0] - sum(numbers[1:])


def multiply(number_list):
    
    numbers = [int(num) for num in number_list]
    
    def recrusive(repeat_num, list_):
    
        if repeat_num == 0:
            return list_[0]
        else:
            return recrusive(repeat_num -1,list_)*list_[repeat_num]
    
    return [recrusive(i,number_list) for i in range(len(number_list))][-1]


def divide(number_list):
    numbers = [int(num) for num in number_list]
    
    def recrusive(repeat_num, list_):
    
        if repeat_num == 0:
            return list_[0]
        else:
            return recrusive(repeat_num -1,list_)/list_[repeat_num]
    
    return [recrusive(i,number_list) for i in range(len(number_list))][-1]



store_result = []
store_num = []
result = 0

for  i,c in enumerate(input_list.split()):
    
    if i < len(input_list.split())-1:

        
        if c == '+' :
            result = plus(store_num)
            store_num = []
            store_result.append(result)
        elif c== "-":
            result = minus(store_num)
            store_num = []
            store_result.append(result)
        elif c =='*':
            result = multiply(store_num)
            store_num = []
            store_result.append(result)     
        elif c == '/':
            result = divide(store_num)
            store_num = []
            store_result.append(result)
        else:
            store_num.append(int(c))
    
    
    
    else:
        if c == '+' :
            result = plus(store_result)
        elif c== "-":
            result = minus(store_result)
        elif c =='*':
            result = multiply(store_result)
        elif c == '/':
            result = divide(store_result)
        
print(str(result))
        
        


### FIXED CODE ###

stack = []
store_num = []
store_result = []

for i,c in enumerate(input().split()): 
        
        def pop_and_stack(list_,num):
                     
            list_.pop()
            list_.pop()
            list_.append(num)
            
            return list_
            
    
        if c == '+' :
            a = stack[-2]
            b = stack[-1]
            num = a+b
            pop_and_stack(stack,num)

        elif c== "-":
            a = stack[-2]
            b = stack[-1]
            num = a-b
            pop_and_stack(stack,num)
        elif c =='*':
            a = stack[-2]
            b = stack[-1]
            num = a*b
            pop_and_stack(stack,num)  
        elif c == '/':
            a = stack[-2]
            b = stack[-1]
            num = a/b
            pop_and_stack(stack,num)
        else:
            stack.append(int(c))
            
print(stack[-1])
N, x = map(int, input().split())
a = list(map(int, input().split()))

total = 0
for i in range(len(a)):
    if (a[i+1]+a[i])>=x:
        if (a[i+1]-(x-a[i]))>=0:
            a[i+1] = a[i+1]-(x-a[i])
            total += x-a[i]
        else:
            a[i+1] = 0
            total += x-a[i]
    else:
        pass
    
print(total)

### FIXED CODE ###

N, x = map(int, input().split())
a = list(map(int, input().split()))

total = 0
for i in range(len(a)-1):
    diff = a[i+1] + a[i] - x
    if diff>0:
        total += diff
        if a[i+1]>=diff:
            a[i+1] = a[i+1]-diff
        else:
            a[i+1] = 0
            a[i] = a[i] -(diff-a[i+1])
    else:
        pass
    
print(total)
N = int(input())
s = raw_input().split()
A = [0]*N

for i in range(N):
    A[i] = int(s[i])

#print N, A

h = 0
t = N-1
lh = 0
lt = 0

for i in range(N):
    if (lh > lt):
        lt += A[t]
        t -= 1
    else:
        lh += A[h]
        h += 1
    #print h, t, lh, lt, A[h+1:t-1]

print abs(lh-lt)


### FIXED CODE ###

s = raw_input().split()
[X, Y] = s
o = [0,0]
o[0] = int(X)
o[1] = int(Y)
#print A, B

p = 0
for i in range(2):
    if o[i] == 1:
        p += 300000
    elif o[i] == 2:
        p += 200000
    elif o[i] == 3:
        p += 100000

if o[0] == 1 and o[1] == 1:
    p += 400000

print p
S = input()
T = input()

count = 0

for i in S,T:
  if S[i] == T[i]:
    count +=1
print(count)

### FIXED CODE ###

S = input()
T = input()

count = 0

if S[0] == T[0]:
  count += 1
if S[1] == T[1]:
  count +=1
if S[2] == T[2]:
  count +=1
print(count)
N = input()
f = sum(map(int, N))
print("Yes" int(N) % f == 0 else "No")


### FIXED CODE ###

N = input()
f = sum(map(int, N))
print("Yes" if int(N) % f == 0 else "No")
from math import factorial
 
def cmb(n, r):
  return factorial(n) // (factorial(n - r) * factorial(r))


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

for i in range(1, K+1):
    ans = cmb(N - K + 1, i) * cmb(K - 1, i - 1) % (10**9+7)
    print(ans)

### FIXED CODE ###

from math import factorial
 
def cmb(n, r):
  return factorial(n) // (factorial(n - r) * factorial(r))


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

for i in range(1, K+1):
    try:
        ans = cmb(N - K + 1, i) * cmb(K - 1, i - 1) % (10**9+7)
        print(ans)
    except:
        print(0)
xkd = list(map(int,input().split()))
xkd[0] = abs(xkd[0])
for i in range(xkd[0] // xkd[2]):
    xkd[0] -= xkd[2]
    xkd[1] -= 1
    if xkd[1] < 1:
      break
ans = xkd[0]
if xkd[1] % 2 != 0:
    ans -= xkd[2]
    if ans > xkd[0] + xkd[2]:
        ans += xkd[2] * 2
print(abs(ans))

### FIXED CODE ###

S = str(input())
ans = 0
if S[1]=="R":
    ans+=1
    if S[0]=="R" or S[2]=="R":
        ans+=1
        if S[0]=="R" and S[2]=="R":
            ans+=1
elif S[0]=="R" or S[2]=="R":
    ans+=1
print(ans)
import numpy as np
from collections import defaultdict
n = int(input())
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))

a_sort = np.sort(a)
b_sort = np.sort(b)

# 1. 回数関係なくそもそも不可能なやつ → no
# 2-a. サイクルは1つだとしても，完璧じゃない組み合わせが1つ以上許容されるやつ → yes
# 2-b. サイクルが2以上にわけられるやつ → yes

# 1
if (a_sort > b_sort).any():
    print('No')
    exit()

# 2-a
if (a_sort[1:] <= b_sort[:-1]).any():
    print('Yes')
    exit()

# 2-b （startをとりあえず1とかにする）
d = defaultdict()
for i in range(n):
    d[a[i]] = b[i]

from_ = 1
count = 0
while True:
    count += 1
    from_ = d[from_]
    if from_ == 1:
        break

if count != n:
    print('Yes')
else:
    print('No')




### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))

a_sort = np.sort(a)
b_sort = np.sort(b)

# 1. 回数関係なくそもそも不可能なやつ → no
# 2-a. サイクルは1つだとしても，完璧じゃない組み合わせが1つ以上許容されるやつ → yes
# 2-b. サイクルが2以上にわけられるやつ → yes

# 1
if (a_sort > b_sort).any():
    print('No')
    exit()

# 2-a
if (a_sort[1:] <= b_sort[:-1]).any():
    print('Yes')
    exit()

# 2-b （startをとりあえず0番目とかにする）
index = b.argsort()
a = a[index]
sort_dict = a.argsort().tolist()
from_ = 0
count = 0
while True:
    count += 1
    from_ = sort_dict[from_]
    if from_ == 0:
        break

if count != n:
    print('Yes')
else:
    print('No')
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    dp = [
        [[0 for _ in range(N * 3 + 10)] for __ in range(N + 10)] for ___ in range(N + 10)
    ]

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for vdp in dp:
        for k in range(N + 1):
            for i in range(W - k * w0 + 1):
                res = max(res, vdp[k][i])
    print(res)


if __name__ == "__main__":
    main()



### FIXED CODE ###

import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    dp = [
        [[0 for _ in range(N * 3 + 10)] for __ in range(N + 10)]
        for ___ in range(N + 10)
    ]
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for k in range(N + 1):
        r = min(W - k * w0, 3 * N + 5)
        if r < 0:
            continue
        for i in range(r + 1):
            res = max(res, dp[N][k][i])
    print(res)


if __name__ == "__main__":
    main()
a,b,c = input()

print(a,b,c)

### FIXED CODE ###

input = input()
a,b,c = [int(x) for x in input.split()]
if (c-a)*(c-b) < 0:
  print('Yes')
else:
  print('No')
N,D = map(int,input().split())
import numpy as np
xlist = [list(map(int,input().split())) for i in range(n)]
xarray = np.array(xlist)
ans = 0
for i in range(n):
  for j in range(i+1,n+1):
    if np.linalg.norm(xarray[i]-xarray[j])%1!=0:
      ans+=1
print(ans)

### FIXED CODE ###

n,d = map(int,input().split())
import numpy as np
xlist = [list(map(int,input().split())) for i in range(n)]
xarray = np.array(xlist)
ans = 0
for i in range(n):
  for j in range(i+1,n):
    if np.linalg.norm(xarray[i]-xarray[j])==int(np.linalg.norm(xarray[i]-xarray[j])):
      ans+=1
print(ans)
N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)

B = sorted(A)
maxA = B[-1]
maxA2 = B[-2]


for i in range(N):
    if A[i] == maxA:
        print(maxA2)
    else:
        print(maxA)

### FIXED CODE ###

r = int(input())
print(3 * r * r)
n,m=map(int,input())
a=list(map(int,input().split()))
b=sum(a)
print(max(-1,n-b))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
b=sum(a)
print(max(-1,n-b))
S = list(input())
ic = ""
for i in range(97, 123):
  if (chr(i) not in S):
    ic = chr(i)
    break
if ic != "":
  print("".join(S) + ic)
else:
  h = S[0]
  for i in range(1,len(S)):
    if h < S[i]:
      h = S[i]
    else:
      ii = i
      break
  print(ii)

### FIXED CODE ###

# 写経#2284578
S = input()
alp = "abcdefghijklmnopqrstuvwxyz"
def h(string, least = 'Z'):
  for c in alp:
    if c not in string:
      if c <= least:
        continue
      return string + c
  if string == "":
    return "-1"
  return h(string[:-1], string[-1])
print(h(S))
N,M = map(int,input().split())
*A, = map(int,input().split())
B = sorted((([2,5,5,4,5,6,3,7,6][a-1],a) for a in A),key = lambda x:(x[0],-x[1]))
i = 1
while i<len(B):
    if B[i][0]==B[i-1][0]:
        B.pop(i)
    else:
        i+=1
i = [0]*(len(B)-1)
ans = []
while i[-1]<B[0][0]:
    tmp = N - sum(j*b[0] for j,b in zip(i,B[1:]))
    if tmp>=0 and tmp%B[0][0] == 0:
        num = ""
        for k,n in sorted(zip([b for _,b in B],[tmp//B[0][0]]+i),key = lambda x:-x[0]):
            num += str(k)*n
        ans.append(int(num))
    i[0]+=1
    for j in range(len(i)-1):
        if i[j]==B[0][0]:
            i[j+1]+=1
            i[j]=0
print(max(ans))

### FIXED CODE ###

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

cost = sorted(list(zip([[2,5,5,4,5,6,3,7,6][a-1] for a in A],A)),key = lambda x: (x[0],-x[1]))

#同じ画数の数字を除く
tmp = len(cost)
i = 1
while i < tmp:
    if cost[i][0] == cost[i-1][0]:
        cost.pop(i)
        tmp = len(cost)
    else:
        i += 1
cost.sort(key = lambda x:-x[1])

dp = [0]+[-10]*(N)
for i in range(2,N+1):
    dp[i] = max([-10]+[dp[i-a]+1 for a,_ in cost if i >= a])

n = N
out = ""
i = 0
while n:
    c , a = cost[i]
    if (n>=c) and (dp[n-c] == dp[n]-1):
        n -= c
        out += str(a)
    else:
        i+=1
print(out)
n ,t = [int(x) for x in input().split()]
arr = [list(map(int, input().split())) for _ in range(n)]

ans = 9999
for i in range(n):
    if arr[i][1] <= t:
        if arr[i][0] <= ans:
            ans = arr[i][0]
if ans = 9999:
    print("TLE")
else:
    print(ans)

### FIXED CODE ###

n ,t = [int(x) for x in input().split()]
arr = [list(map(int, input().split())) for _ in range(n)]

ans = 9999
for i in range(n):
    if arr[i][1] <= t:
        if arr[i][0] <= ans:
            ans = arr[i][0]
if ans == 9999:
    print("TLE")
else:
    print(ans)
from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]


def sgn(x):
    if x > 0:
        return 0
    elif x < 0:
        return 1
    else:
        return 2


pl = []
mn = []
zr = []

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)
    else:
        zr.append(x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)


b = [(abs(a[i]), sgn(a[i])) for i in range(n)]
b = sorted(b, reverse=True)

c = [0, 0, 0]
for i in range(k):
    c[b[i][1]] += 1
    if c[2] > 1:
        print(0)
        exit()


def solve(c):
    ans = 1
    for i in range(c[0]):
        ans *= pl[i]
        ans %= mod
    for i in range(c[1]):
        ans *= mn[i]
        ans %= mod
    return ans


if c[1] % 2 == 0:
    print(solve(c))
elif c[0] < len(pl):
    c[0] += 1
    c[1] -= 1
    print(solve(c))
elif 0 < c[0] and c[0] == len(pl) and c[1] < len(mn):
    c[0] -= 1
    c[1] += 1
    print(solve())
else:
    if len(zr) > 0:
        print(0)
        exit()
    else:
        tmp = 1
        for i in range(k):
            tmp *= mn[-i-1]
            tmp %= mod
        print((-tmp) % mod)


### FIXED CODE ###

from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]


def sgn(x):
    if x >= 0:
        return 0
    elif x < 0:
        return 1


pl = []
mn = []

for x in a:
    if x >= 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)


b = [(abs(a[i]), sgn(a[i])) for i in range(n)]
b = sorted(b, reverse=True)

c = [0, 0]
for i in range(k):
    c[b[i][1]] += 1


def solve(c):
    ans = 1
    for i in range(c[0]):
        ans *= pl[i]
        ans %= mod
    for i in range(c[1]):
        ans *= mn[i]
        ans %= mod
    if c[1] % 2:
        ans = (-ans) % mod
    return ans


if c[1] % 2 == 0:
    print(solve(c))
    exit()

if len(mn) == n and k % 2:
    tmp = 1
    for i in range(k):
        tmp *= mn[-i-1]
        tmp %= mod
    ans = -tmp
    print(ans % mod)
    exit()

ans = 0

chk1 = False
chk2 = False

if c[0] <= len(pl) - 1:
    chk1 = True

if 0 < c[0] and c[1] <= len(mn)-1:
    chk2 = True

if chk1 and chk2:
    tmp1 = pl[c[0]]*pl[c[0]-1]
    tmp2 = mn[c[1]]*mn[c[1]-1]
    if tmp1 > tmp2:
        c[0] += 1
        c[1] -= 1
        print(solve(c))
    else:
        c[0] -= 1
        c[1] += 1
        print(solve(c))
elif chk1:
    c[0] += 1
    c[1] -= 1
    print(solve(c))
elif chk2:
    c[0] -= 1
    c[1] += 1
    print(solve(c))
else:
    print(solve(c))
n = int(input())
a = sorted(list(map(int, input().split(" "))))
idx = 0
while True:
    removes = []
    v = a[idx]
    for target in a:
        if target % v == 0:
            removes.append(target)
    removes.remove(v)
    if removes:
        if removes[0] == v:
            removes.append(v)
        for target in removes:
            a.remove(target)
    if len(a) == 0 or a[-1] == v:
        break
    idx += 1
print(len(a))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split(" ")))
a_max = max(A)
cnts = [0] * (a_max + 1)
for a in A:
    v = a
    while v <= a_max:
        cnts[v] += 1
        v += a
cnt = 0
for a in A:
    if cnts[a] == 1:
        cnt += 1
print(cnt)
A, B, C = map(int(),input().split())
print(min(B//A,C))

### FIXED CODE ###

A, B, C = map(int,input().split())
print(min(B//A,C))
a=int(input("a:"))
b=int(input("b:"))
area=a*b
pm=2*a+2*b



### FIXED CODE ###

a,b=map(int,input().split())
area=a*b
pm=2*a+2*b
print(area,pm)
K,S = map(int,input().split())
sum=0
for x in range(0,K+1):
    for y in range(x,K+1):
       if x+y-S<=0:
           z = S-x-y
            
            if x==y and y==z and z==x:
              sum+=1
            elif x!=z and z!=y and y!=x:
              sum+=6
            else:
              sum+=3

print(sum)

### FIXED CODE ###

K,S = map(int,input().split())
sum=0
for x in range(0,K+1):
    for y in range(0,K+1):
        z = S-x-y

        if z>=0 and z<=K:
            sum+=1


print(sum)
N=int(input())
a=list(map(int,input().split()))

l=sorted(a)

ans=1
targetindex=0
t=l[targetindex]

for i in range (N-targetindex):
    c=l[targetindex+i]
    _ans=1
    if c-t<=2:
        pass
    else:
        _ans=i
        
    if _ans>ans:
        ans=_ans
        targetindex=targetindex+i
        t=[targetindex]
    else:
        pass
print(ans)


### FIXED CODE ###

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

l=[0]*((10**5)+2)

for v in a:
    l[v]+=1
    l[v+1]+=1
    l[v+2]+=1

print(max(l))
4
20 18 2 18

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted(A, key=lambda x: -x)
    a, b = 0, 0
    for i in range(N):
        if i % 2 == 0:
            a += A[i]
        else:
            b += A[i]
    print(a-b)


if __name__ == '__main__':
    main()
N = int(input())
S = input()
A = [[],[],[]]
ans = 0
for i in range(N):
    if S[i] == 'R':
        A[0].append(i)
    elif S[i] == 'G':
        A[1].append(i)
    else:
        A[2].append(i)

for i in A[0]:
    for j in A[1]:
        for k in A[2]:
            if  (i < j and j < k) or (k < j and j < i):
                if abs(i-j) != abs(j-k):
                    ans += 1
            elif (i < k and k < j) or (j < k and k < i):
                if abs(i-k) != abs(k-j):
                    ans += 1
            elif (j < i and i < k) or (k < i and i < j):
                if abs(j-i) != abs(k-i):
                    ans += 1

print(ans)

### FIXED CODE ###

N = input()
for i in range(3):
  if int(N[i]) == 7:
    print('Yes')
    exit()
print('No')
from bisect import*
l = sorted(map(int, open(0).read().split()[1:]))
print(sum(max(0, bisect_left(l, l[i] + l[j]) - j - 1) for i in range(n) for j in range(i+1, n)))

### FIXED CODE ###

from bisect import*
n, *l = map(int, open(0).read().split())
l.sort();c=0
for i in range(n):
  for j in range(i+1, n):
    d = bisect_left(l, l[i] + l[j])
    c += max(0, d-j-1)
print(c)
x, y, m = map(int,input().split())
mat = []
r = [0]*x
c = [0]*y
smx = 0
smy = 0
for _ in range(m):
    p, q = map(int,input().split())
    p -= 1
    q -= 1
    mat.append((p,q))
    r[p] += 1
    c[q] += 1
    smx = max(smx,r[p])
    smy = max(smy,c[q])
xs = []
ys = []
for i in range(x):
    if smx == r[i]: xs.append(i)
for i in range(y):
    if smy == c[i]: ys.append(i)

ans = smx + smy - 1

for h in xs:
    for w in ys:
        if (h, w) in mat: continue
        print(ans + 1)
        end()
print(ans)


### FIXED CODE ###

x, y, m = map(int,input().split())
mat = set()
r = [0]*x
c = [0]*y
smx = 0
smy = 0
for _ in range(m):
    p, q = map(int,input().split())
    p -= 1
    q -= 1
    mat.add((p,q))
    r[p] += 1
    c[q] += 1
    smx = max(smx,r[p])
    smy = max(smy,c[q])
xs = []
ys = []
for i in range(x):
    if smx == r[i]: xs.append(i)
for i in range(y):
    if smy == c[i]: ys.append(i)

ans = smx + smy - 1

for h in xs:
    for w in ys:
        if (h, w) in mat: continue
        print(ans + 1)
        exit()
print(ans)
init_input()

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

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1))

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans += (a * c) % mod

print(ans % mod)

### FIXED CODE ###

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

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

dp[n] = [0, 0, 0, 1]
for i in range(n-1, -1, -1):
    if S[i] == '?':
        dp[i][3] =  dp[i+1][3] * 3 % mod
        dp[i][2] = (dp[i+1][2] * 3 + dp[i+1][3]) % mod
        dp[i][1] = (dp[i+1][1] * 3 + dp[i+1][2]) % mod
        dp[i][0] = (dp[i+1][0] * 3 + dp[i+1][1]) % mod
    elif S[i] == 'C':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] = (dp[i+1][2] + dp[i+1][3]) % mod
        dp[i][1] =  dp[i+1][1] % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'B':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] =  dp[i+1][2] % mod
        dp[i][1] = (dp[i+1][1] + dp[i+1][2]) % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'A':
        dp[i][3] =  dp[i+1][3]
        dp[i][2] =  dp[i+1][2]
        dp[i][1] =  dp[i+1][1]
        dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % mod
print(dp[0][0])
n,k = map(int, input().split())
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**7+7 #出力の制限
N = 10**4
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 )

for i in range(1,k+1):
    a = cmb(n-k+1,i)
    b = cmb(k-1,i-1)
    print((a*b)%mod)

### FIXED CODE ###

n,k = map(int, input().split())
mod = 10**9+7
from scipy.misc import comb

for i in range(1,k+1):
    print((comb(n-k+1,i,exact=True)*comb(k-1,i-1,exact=True))%mod)
N = input()
for i in xrange(N):
    b, c = 0, 0
    for j in map(int, raw_input().split()):
        if b[-1] < j: b = j
        elif c[-1] < j: c = j
        else: break
    else:
        print 'YES'
        continue
    print 'NO'

### FIXED CODE ###

for i in xrange(input()):
    b, c = 0, 0
    for j in map(int, raw_input().split()):
        if b < j: b = j
        elif c < j: c = j
        else: break
    else:
        print 'YES'
        continue
    print 'NO'