Harryxun/stf_run huggingface dataset:
N = int(input())
As = list(map(int, input()))

A_sorted = sorted(As)
med1 = A_sorted[N//2]
med2 = A_sorted[N//2+1]

for A in As:
  if A <= med1:
    print(med2)
  else:
    print(med1)

### FIXED CODE ###

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

A_sorted = sorted(As)
med1 = A_sorted[N//2-1]
med2 = A_sorted[N//2]

for A in As:
  if A <= med1:
    print(med2)
  else:
    print(med1)
N = int(input())
S = list(input().split())
d = S[0]

for i in range(1, N-1):
  if S[i] != S[i-1]:
    d = d + S[i]
    
print(len(d))

### FIXED CODE ###

N = int(input())
S = input()
d = S[0]

for i in range(1, N):
  if S[i] != S[i-1]:
    d = d + S[i]
    
print(len(d))
def is_symmetric(board):
    for i in range(N):
        for j in range(i, N):
            if board(j, i) != board(i, j):
                return False
    return True


def translate(board, a, b):
    def get(i, j):
        return board[(i + a) % N][(j + b) % N]
    
    return get


def solve(board):
    ans = 0
    for a in range(N):
        if is_symmetric(translate(board, a, 0)):
            ans += N - a
    for b in range(N):
        if b == 0:
            continue
        if is_symmetric(translate(board, 0, b)):
            ans += N - b
    return ans


N = int(input())
board = []
for i in range(N):
    board.append(input())


print(solve(board))

### FIXED CODE ###

from collections import Counter

def c2(a):
    if a <= 1:
        return 0
    return a * (a - 1) / 2

def solve(arr):
    cum = [0]
    s = 0
    for i in arr:
        s += i
        cum.append(s)

    return int(sum(c2(v) for k, v in Counter(cum).items()))

input()
print(solve([int(i) for i in input().split()]))
N,K = [int(input()) for i in range(2)]
h = list(map(int, input().split()))
 
num =0
for i in range(N):
    if h[i]>K or h[i] == K:
        num =num+ 1
print(num)

### FIXED CODE ###

N=int(input())
if N%2==0:
    print(0.5)
else:
    print((N+1)/(2*N))
import sys
N = int(sys.stdin.read().rstrip())
a = [int(x) in x for stdin.readline().rstrip().split(' ')]
d = [abs(sum(a)/float(N) - ai) for ai in a]

if len(set(d))==1:
	print(0)
else:
	 print(d.index(min(d)))

### FIXED CODE ###

import sys
N = int(sys.stdin.readline().rstrip())
a = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
d = [abs(sum(a)/float(N) - ai) for ai in a]

if len(set(d))==1:
  print(0)
else:
  print(d.index(min(d)))
#E 
n,p=map(int,input().split())
s=input()



#D
def main():
  s=input()
  q=int(input())
  turn = 2

  for _ in [0]*q:
      query = input()
      try:
          t = int(query)
          turn = 3 - turn
      except ValueError:
          t,f,c = map(str,query.split())
          if (int(f) + turn)% 2  == 0:
              s = s + c
          else:
              s = c + s
  if turn == 2:
      print(s)
  else:
      print(s[::-1])
main()

### FIXED CODE ###

def main():
  from collections import deque
  s=input()
  q=int(input())
  turn = 2
  d=deque(s)

  for _ in [0]*q:
      query = input()
      if query[0] == "1":
          t = int(query)
          turn = 3 - turn
      else:
          t,f,c = map(str,query.split())
          if (int(f) + turn)% 2  == 0:
              d.append(c)
          else:
              d.appendleft(c)
  if turn == 2:
      print("".join(d))
  else:
      print("".join(list(d)[::-1]))
main()
def resolve():
    '''
    code here
    '''
    from functools import lru_cache

    N, M = [int(item) for item in input().split()]
    As = [int(input()) for _ in range(M)]
    memo = [1 for _ in range(N+1)]

    for item in As:
        memo[item] = 0

    res_list = []
    for i in range(1,N+1):
        if i == 1 and memo[i] == 0:
            memo[i] = 0
            res_list.append(2)
        elif memo[i] == 0:
            memo[i] = 0
            res_list.append(memo[i-1])
        else:
            memo[i] += memo[i-1]
    else:
        res_list.append(memo[N])

    
    @lru_cache
    def cal(num):
        if num <= 1:
            return 0
        elif num == 2:
            return 1
        elif num == 3:
            return 2
        else:
            return cal(num-1) + cal(num-2)
    
    res = 1
    for item in res_list:
        res *= cal(item)
    print(res % (10**9 + 7))



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from functools import lru_cache
    import sys
    sys.setrecursionlimit(10**6)

    N, M = [int(item) for item in input().split()]
    As = [int(input()) for _ in range(M)]
    memo = [False for _ in range(N+1)]

    for item in As:
        memo[item] = True

    res_list = []

    prev = 0
    for i in range(1,N+1):
        if memo[i] == True:
            res_list.append(i-1 - prev)
            prev = i+1
    else:
        if memo[N] == False and memo[N] == False:
            res_list.append(N - prev)

    @lru_cache
    def cal(num):
        if 0 <= num <= 1:
            return 1
        elif num == -1:
            return 0
        else:
            return cal(num-1) + cal(num-2)
    # print(res_list)
    res = 1
    for item in res_list:
        res *= cal(item)% (10**9 + 7)

    print(res % (10**9 + 7))



if __name__ == "__main__":
    resolve()
n,a,b=int(input()),[sorted(list(map(int,input().split())))for i in range(3)],[[],[]]
x=0
for i in range(n):
  while a[2][i]>a[1][x]:
    b[1].append(n-i)
    x+=1
    if x==n:break
  if x==n:break
for i in range(1,n):b[1][n-i-1]+=b[1][n-i]
x=0
for i in range(n):
  while a[1][i]>a[0][x]:
    b[0].append(b[1][i])
    x+=1
    if x==n:break
  if x==n:break
print(sum(b[0]))

### FIXED CODE ###

n,a=int(input()),[sorted(list(map(int,input().split())))for i in range(3)]
b=[[],[]]
x=0
for i in range(n):
  while a[2][i]>a[1][x]:
    b[1].append(n-i)
    x+=1
    if x==n:break
  if x==n:break
for i in range(n-len(b[1])):b[1].append(0)
for i in range(1,n):b[1][n-i-1]+=b[1][n-i]
x=0
for i in range(n):
  while a[1][i]>a[0][x]:
    b[0].append(b[1][i])
    x+=1
    if x==n:break
  if x==n:break
print(sum(b[0]))
N, K = map(int, input().split())
while N>K:
  a=N/K
  b+=1
print(b)  

### FIXED CODE ###

N, K = map(int, input().split())
b=0
while N>0:
  N=N//K
  b+=1
print(b)
A = map(int, input().split())
print(max(A) - min(A))

### FIXED CODE ###

a = list(map(int, input().split()))
print(abs(max(a) - min(a)))
raw = int(raw_input().split(""))
tmp = 1
for i in range(len(raw) - 1):
  div = abs(raw[i] - raw[i-1])
  if div >= tmp:
    tmp = div
print tmp

### FIXED CODE ###

num = int(raw_input())
law = raw_input().split(" ")
tmp = 0
raw = []
for i in law:
    raw.append(int(i))
for i in range(num):
    for j in range(i, num):
        div = abs(raw[i] - raw[j])
        if div >= tmp:
            tmp = div
print tmp
from collections import defaultdict
N = int(input())
D = []
for i in range(N):
    x, y = map(int, input().split())
    D.append((x, y))

d = defaultdict(int)
for i in range(N):
    for j in range(i + 1, N):
        d[(D[i][0] - D[j][0], D[i][1] - D[j][1])] += 1

print(N - max(d.values()))


### FIXED CODE ###

N = int(input())
if N == 1:
    print(1)
    exit()
D = []
for i in range(N):
    x, y = map(int, input().split())
    D.append((x, y))
D = sorted(D)

d = set()
for i in range(N):
    for j in range(N):
        d.add((D[i][0] - D[j][0], D[i][1] - D[j][1]))


d = list(d)
num = float('inf')
for p, q in d:
    if p == 0 and q == 0:
        continue
    used = [0] * N
    prex, prey = D[0][0], D[0][1]
    used[0] = 1
    tmp = 1
    for k in range(N - 1):
        for i in range(N):
            if used[i]:
                continue
            if D[i][0] - prex == p and D[i][1] - prey == q:
                prex = D[i][0]
                prey = D[i][1]
                used[i] = 1
                break
        else:
            tmp += 1
            for i in range(N):
                if not used[i]:
                    prex = D[i][0]
                    prey = D[i][1]
                    used[i] = 1
                    break
    num = min(tmp, num)

print(num)
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab = sorted(ab, key=lambda ab:ab[0])

ans = 0
total = 0
for i in range(n):
  num = m-toal
  if ab[i][1]<=num:
    total += ab[i][1]
    ans += ab[i][0]*ab[i][1]
  else:
    total += num
    ans += num*ab[i][1]
    break
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
drink = [list(map(int,input().split())) for _ in range(n)]
drink = sorted(drink, key=lambda drink:drink[0])
money = 0
total = 0
for i in range(n):
  if total+drink[i][1]<m:
    total += drink[i][1]
    money += drink[i][1]*drink[i][0]
  else:
    money += drink[i][0]*(m-total)
    print(money)
    exit()
h,w=map(int,input())
r=[]
for i in range(h):
    r.append(list(input()))
t=[]
for i in range(h):
    for j in range(w):
        if r[i][j]=='#':
            t.append([i,j])
op=[[[0,0]]]
for i in range(h+w-2):
    tmp=[]
    for j in op:
        tmp.append(j+[[j[-1][0]+1,j[-1][1]]])
        tmp.append(j+[[j[-1][0],j[-1][1]+1]])
    op=tmp
for i in op:
    if sorted(i)==sorted(t):
        print('Possible')
        exit()
print('Impossible')

### FIXED CODE ###

h,w=map(int,input().split())
r=[]
for i in range(h):
    r.append(list(input()))
t=[]
for i in range(h):
    for j in range(w):
        if r[i][j]=='#':
            t.append([i,j])
op=[[[0,0]]]
for i in range(h+w-2):
    tmp=[]
    for j in op:
        tmp.append(j+[[j[-1][0]+1,j[-1][1]]])
        tmp.append(j+[[j[-1][0],j[-1][1]+1]])
    op=tmp
for i in op:
    if sorted(i)==sorted(t):
        print('Possible')
        exit()
print('Impossible')
def shuffle(strings, num):
  tmp = strings[0:num]
  new_strings = strings.replace(tmp, "") + tmp
  return new_string

strings = raw_input()
while(True):
  num = raw_input()
  if type(num) == str:
    print strings
    strings = num
    continue
  elif num == '-':
    break
  strings = shuffle(strings, num)

### FIXED CODE ###

while True :
	s = raw_input()
	if s == '-' :
		break
	m = int(raw_input())
	for i in range(m) :
		h = int(raw_input())
		s = s[h:] + s[:h]
	print s
print("Aa"[int(ord(input())>95))


### FIXED CODE ###

print("Aa"[ord(input())>95])
### INPUT
N = int(input())
A = list(map(int,input().split()))
cont = 0
CN = [0]
b = N-1
### MAIN
for i in range(b):
    s = i
    while A[s]>=A[s+1] and s+1!=b:
        cont = cont + 1
        s = 1 + s
    if  (A[s]>=A[s+1]) and (s+1==b):
        cont =cont + 1
    if  cont != 0:
        CN.extend([cont])
        cont = 0
### MAX

print(max(CN))


### FIXED CODE ###

t = list(input())
s = list(input())
cnt = 0
for a in range(3):
    if s[a] == t[a]:
        cnt = cnt + 1

print(cnt)
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, p: "List[int]", S: "List[str]"):
    d = dict([(i, []) for i in set(p)])
    for _p, _s in zip(p, S):
        d[_p].append(_s)
    # print(d)
    A = 0
    W = 0
    for v in d.values():
        _a = v.index('AC')
        # print(_a)
        A += 1
        W += _a
    print(A, W)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    p = [int()] * (M)  # type: "List[int]"
    S = [str()] * (M)  # type: "List[str]"
    for i in range(M):
        p[i] = int(next(tokens))
        S[i] = next(tokens)
    solve(N, M, p, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, p: "List[int]", S: "List[str]"):
    A = [False] * (N+1)
    W = [0] * (N+1)
    wans = 0
    for _p, _s in zip(p, S):
        if A[_p]:
            continue
        if _s == 'WA':
            W[_p] += 1
        else:
            A[_p] = True
            wans += W[_p]
    ans = sum(A)
    print(ans, wans)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    p = [int()] * (M)  # type: "List[int]"
    S = [str()] * (M)  # type: "List[str]"
    for i in range(M):
        p[i] = int(next(tokens))
        S[i] = next(tokens)
    solve(N, M, p, S)

if __name__ == '__main__':
    main()
n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
nl = set(range(nl))
for i in nl:
    t[i + 1] = t[i] + (1 if s[i:i + 2] == 'AC' else 0)
ql = set(range(q))
for i in ql:
    l1, l2 = map(int, input().split())
    ans = t[l2-1] - t[l1-1]
    print(ans)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
nl = set(range(n))
for i in nl:
    t[i + 1] = t[i] + (1 if s[i:i + 2] == 'AC' else 0)
ql = set(range(q))
for i in ql:
    l1, l2 = map(int, input().split())
    ans = t[l2-1] - t[l1-1]
    print(ans)
x, k, d = map(int, input().split())

if x >= 0:
    if x >= k * d:
        print(x - k * d)
    else:
        func(x, k, d)
        # q, mod = divmod(x, d)
        # k -= q
        # if k % 2 == 0:
        #     print(mod)
        # else:
        #     print(abs(mod - d))
else:
    if abs(x) >= k * d:
        print(abs(x) - k * d)
    else:
        func(x, k, d)
        # q, mod = divmod(abs(x), d)
        # k -= q
        # if k % 2 == 0:
        #     print(mod)
        # else:
        #     print(abs(mod - d))


def func(x, k, d):
    q, mod = divmod(abs(x), d)
    k -= q
    if k % 2 == 0:
        print(mod)
    else:
        print(abs(mod - d))
    return 0


### FIXED CODE ###

x, k, d = map(int, input().split())

if x == 0:
    if k % 2 == 0:
        print(0)
    else:
        print(d)
elif x > 0:
    if x >= k * d:
        print(x - k * d)
    else:
        q, mod = divmod(x, d)
        k -= q
        if k % 2 == 0:
            print(mod)
        else:
            print(abs(mod - d))
elif x < 0:
    if abs(x) >= k * d:
        print(abs(x + k * d))
    else:
        q, mod = divmod(abs(x), d)
        k -= q
        if k % 2 == 0:
            print(mod)
        else:
            print(abs(mod - d))
import math
r=int(input())
print("{0:8f} {1:8f}".format(math.pi*r*r,r*2*math.pi))

### FIXED CODE ###

import math
r=float(input())
print("{0:8f} {1:8f}".format(math.pi*r*r,r*2*math.pi))
import sys
s = []
for i in sys.stdin:
 s.append(input().lower())

for i in range(ord('a'), ord('z')+1):
 print("{0} : {1}".format(chr(i), s.count(chr(i))))

### FIXED CODE ###

import sys 
dataset = sys.stdin.readlines()

for s in range(ord('a'), ord('z') + 1):
 count = 0
 for data in dataset:
  count += data.lower().count(chr(s))
 print("{0} : {1}".format(chr(s), count))
from itertools import chain
n=int(input())
an= [list(input()) for _ in range(n)]
a=list(chain.from_iterable(an))
nex=[]
k=1
for i in range(len(a)):
    #if k-1==-1:k-1=0
    nex.append(a[k-1])
    k=nex[-1]
    if nex[-1]==2:
        print(len(nex))
        break
    elif len(nex)>=n:print(-1)
    else:pass

### FIXED CODE ###

n=int(input())
a = [int(input()) for _ in range(n)]
nex=[]
k=1
for i in range(len(a)):
    nex.append(a[k-1])
    k=nex[-1]
    if nex[-1]==2:
        print(len(nex))
        break
    elif len(nex)>=n:print(-1)
    else:pass
N,T=map(int,input().split())
d=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  d[i]=[a,b]

d=sorted(d,key=lambda x:x[a])
dp=[-1]*(3000*2+5)
dp[0]=0
for i in range(len(d)):
  for j in range(T-1,-1,-1):
    if dp[j]!=-1:
      if dp[j]+d[i][1]>dp[j+d[i][0]]:
        dp[j+d[i][0]]=dp[j]+d[i][1]
      
print(max(dp))

### FIXED CODE ###

N,T=map(int,input().split())
d=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  d[i]=[a,b]

import numpy as np
d=sorted(d,key=lambda x:x[0])
dp=np.zeros(T,dtype=int)
ans=0
for i in range(len(d)):
  t=d[i][0]
  v=d[i][1]
  ans=max(ans,dp.max()+v)
  np.maximum(dp[:-t]+v,dp[t:],out=dp[t:])

print(ans)
from sys import stdin
d=int(stdin.readline().rstrip())
extent=" Eve"*(25-d)
print(f"Christmas{extent}")

### FIXED CODE ###

from sys import stdin
d=int(stdin.readline().rstrip())
extent="Eve "*(25-d)
print("Christmas",extent)
n, k = map(int, input().split())
h = [int(i) for i in input().split()]
ans = 0
for j in h:
    for j >= k:
        ans += 1
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]
ans = 0
for j in h:
    if j >= k:
        ans += 1
print(ans)
n, k = map(int, input().split())
s = input()
s[k] = s[k].lower()

### FIXED CODE ###

n, k = map(int, input().split())
s = list(input())
s[k-1] = s[k-1].lower()
print("".join(s))
N=int(input())
*A,=map(int,input().split())

A.sort()
ans=N
i=0
while i<len(A):
    if i==0 and A[i]==A[i+1]:
        ans-=1
        i+=1
        continue
    for a in A[:i]:
        if A[i]%a==0:
            ans-=1
            break
        if a>A[i]//2+1:
            break
    i+=1

print(ans)

### FIXED CODE ###

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

A.sort()
count=[0]*(A[-1]+1)
i=0
while i<N:
    j=A[i]
    if 2<=count[j]:
        i+=1
        continue
    k=1
    while j*k<=A[-1]:
        count[j*k]+=1
        k+=1
    i+=1

print(sum(count[a]==1 for a in A))
N = int(input())
SP = [list(input().split()) for i in range(N)]

SPsort = sorted(SP, key = lambda x:x[0])

for i in range(N):
    print(SP.index(SPsort[i])) + 1

### FIXED CODE ###

N = int(input())
SP = [list(input().split()) for i in range(N)]

for row in SP:
    row[1] = int(row[1])

hoge = sorted(SP, key = lambda x:x[1], reverse = True)
SPsort = sorted(hoge, key = lambda x:x[0])

for i in range(N):
    print(SP.index(SPsort[i]) + 1)
n=int(input())
h=list(map(int,input().split()))
ans=0
kari=0
inde=0
while 1:
    suuzi=h[inde]
    if h[inde+1]<=suuzi:
        kari+=1
    elif ans<kari:
        ans=-kari
        kari=0
    if inde==n-1:
        break
    inde+=1
print(ans)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
ans=0
kari=0
for i in range(n-1):
        if h[i+1]<=h[i]:
            kari+=1
        else:
            if ans<kari:
                ans=kari
            kari=0
        
       
print(max(ans,kari))
n,c = map(int,input().split())
table = [0 for i in range(10**5+1)]
chan = [[] for _ in range(c+2)]

for _ in range(n):
    s,t,c = map(int,input().split())
    chan[c].append([s,t])

# 同チャンネルの連続番組を統合する
times = []
for i in range(c+2):
    arr = chan[i]
    if chan[i]==[] : continue
    for i in range(len(arr)):
        if i == len(arr)-1 : break
        if arr[i][1] == arr[i+1][0]:
            arr[i+1] = [arr[i][0], arr[i+1][1]]
            arr[i] = [1,0]
    times += arr

# いもす法
for ele in times:
    table[ele[0]] += 1
    table[ele[1]+1] -= 1

# 累積和の計算
ans = 0
for i in range(len(table)):
    if i==0 : continue
    table[i] += table[i-1]
    ans = max(ans, table[i])

print(ans)



### FIXED CODE ###

import numpy as np

n,c = map(int,input().split())
table = np.zeros(10**5+2, dtype=np.int32)
chs = [[] for _ in range(c+1)]

for _ in range(n):
    s,t,c = map(int,input().split())
    chs[c].append([s,t])

# 同チャンネル内の連続番組を合体
times = []
for ch in chs:
    if not ch: continue
    ch.sort()
    for i in range(len(ch)):
        if i == 0: continue
        if ch[i-1][1] == ch[i][0]:
            ch[i] = [ch[i-1][0], ch[i][1]]
            ch[i-1] = []
    for arr in ch:
        if not arr: continue
        times.append(arr)

# いもす法
for arr in times:
    table[arr[0]] += 1
    table[arr[1]+1] -= 1

# 累積和の最大値
ans = table.cumsum().max()

print(ans)
k = int(input())

def fun(k):
    lun_luns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    index = 0
    while True:
        if len(lun_luns) >= k:
            break
        num = lun_luns[index]
        mod = num%10
        if mod == 9:
            lun_luns.extend([n+mod-1, n+mod])
        elif mod == 0:
            lun_luns.extend([n, n+1])
        else:
            lun_luns.extend([n+mod-1, n, n+mod+1])
        index += 1
    
    return lun_luns

print(fun(k)[k-1])

### FIXED CODE ###

k = int(input())

def fun(k):
    lun_luns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    index = 0
    while True:
        if len(lun_luns) >= k:
            break
        num = lun_luns[index]
        mod = num%10
        n = num*10
        if mod == 9:
            lun_luns.extend([n+mod-1, n+mod])
        elif mod == 0:
            lun_luns.extend([n, n+1])
        else:
            lun_luns.extend([n+mod-1, n+mod, n+mod+1])
        index += 1
    
    return lun_luns[k-1]

print(fun(k))
a = list(input())

dp = [[0]*3 for i in range(len(a)+1)]

ppp ~ 1
for i in range(len(a))[::-1]:
	if a[i] == "A":
		dp[i][0] += dp[i+1][0] + dp[i+1][1]
		dp[i][1] += dp[i+1][1]
		dp[i][2] += dp[i+1][2]
	elif a[i] == "B":
		dp[i][0] += dp[i+1][0]
		dp[i][1] += dp[i+1][1] + dp[i+1][2]
		dp[i][2] += dp[i+1][2]
	elif a[i] == "C":
		dp[i][0] += dp[i+1][0]
		dp[i][1] += dp[i+1][1]
		dp[i][2] += dp[i+1][2] + ppp
	else:
		dp[i][0] += 3 * dp[i+1][0] + dp[i+1][1]
		dp[i][1] += 3 * dp[i+1][1] + dp[i+1][2]
		dp[i][2] += 3 * dp[i+1][2] + ppp
		ppp *= 3
		ppp %= 10**9+7
	for j in range(3):
		dp[i][j] %= (10**9 + 7)
print(dp[0][0] % (10**9 + 7))

### FIXED CODE ###

a = list(input())

dp = [[0]*3 for i in range(len(a)+1)]

ppp = 1
for i in range(len(a))[::-1]:
	if a[i] == "A":
		dp[i][0] += dp[i+1][0] + dp[i+1][1]
		dp[i][1] += dp[i+1][1]
		dp[i][2] += dp[i+1][2]
	elif a[i] == "B":
		dp[i][0] += dp[i+1][0]
		dp[i][1] += dp[i+1][1] + dp[i+1][2]
		dp[i][2] += dp[i+1][2]
	elif a[i] == "C":
		dp[i][0] += dp[i+1][0]
		dp[i][1] += dp[i+1][1]
		dp[i][2] += dp[i+1][2] + ppp
	else:
		dp[i][0] += 3 * dp[i+1][0] + dp[i+1][1]
		dp[i][1] += 3 * dp[i+1][1] + dp[i+1][2]
		dp[i][2] += 3 * dp[i+1][2] + ppp
		ppp *= 3
		ppp %= 10**9+7
	for j in range(3):
		dp[i][j] %= (10**9 + 7)
print(dp[0][0] % (10**9 + 7))
#coding utf-8

a,b = map(int, input().split())
# d = list(map(int,input().split()))

x = []

x.append(a*b)
x.append(a/b)
x.append(a+b)
x.append(a-b)

print(max(x))

### FIXED CODE ###

#coding utf-8

a,b = map(int, input().split())
# d = list(map(int,input().split()))

x = [a*b, a+b, a-b]

print(max(x))
N, W = (int(i) for i in input().split())
bagage = [[int(i) for i in input().split()] for _ in range(N)]
weight = []
value = []
for b in bagage:
    value.append(b[0])
    weight.append(b[1])

dp = [[0]*10010 for i in range(100)]

for j in range(W):
    dp[N][j] = 0

for i in range(N-1, -1, -1):
    for j in range(0, W+1, 1):
        if j < weight[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-weight[i]] + value[i])

print(dp[0][W])


### FIXED CODE ###

N, W = (int(i) for i in input().split())
bagage = [[int(i) for i in input().split()] for _ in range(N)]
weight = []
value = []
for b in bagage:
    value.append(b[0])
    weight.append(b[1])

dp = [[0]*10010 for i in range(110)]

for j in range(W):
    dp[N][j] = 0

for i in range(N-1, -1, -1):
    for j in range(0, W+1, 1):
        if j < weight[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-weight[i]] + value[i])

print(dp[0][W])
n,x,m=map(int,input().split())
ans=0
p=0
l=[x]
if x%m==0:
  print(x)
else:
  for i in range(1,n):
    s=(l[i-1]**2)%m
    if s==0:
      p=1
      break
    if s in l:
      break
    else:
      l.append(s)
  if p==0:
    t=sum(l[1:])
    k=(n-1)//(len(l)-1) #ループ何回回るか
    j=(n-1)%(len(l)-1)
    ans=x+t*k+sum(l[1:j+1])
    print(ans)
  else:
    print(sum(l))


### FIXED CODE ###

n,x,m=map(int,input().split())
order=[-1 for i in range(m)] #-1のところにはまだ対応する余りがない、余りは高々m通り
index=0 #何番目に出た余りなのかを示す
a=[] #数列
while order[x]==-1: #ループが完成するまでは
  order[x]=index #xはindex番目の余り
  a.append(x)
  x=(x**2)%m
  index+=1
tmp=sum(a[order[x]:index]) #1ループの和、xがループの始点の余り
t=index-order[x] #1ループの長さ
if n-1<order[x]: #ループが完成しない場合
  print(sum(a[:n]))
else:
  sum1=sum(a[:order[x]]) #ループの前の和
  x1=n-order[x] #ループ部分の長さ
  n1=x1//t #ループの回数
  n2=x1%t
  print(sum1+n1*tmp+sum(a[order[x]:order[x]+n2]))