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

import bisect

n = int(input())

a = sorted([int(x) for x in input().split()])
b = sorted([int(x) for x in input().split()])
c = sorted([int(x) for x in input().split()])

res = 0
for cc in c:
    b_res = bisect.bisect_left(b, cc)
    for bb in b[:b_res]:
        res += (bisect.bisect_left(a, bb))

print(res)

### FIXED CODE ###

import bisect

num = int(input())
top = sorted([int(x) for x in input().split()])
middle = sorted([int(x) for x in input().split()])
bottom = sorted([int(x) for x in input().split()])


# middleの配列でループを回したほうが早い(topとbottomを同時に処理できるため)
res = 0
for i in middle:
    index = bisect.bisect_left(top, i)
    index2 = len(bottom)-bisect.bisect_right(bottom, i)
    res += index*index2

print(res)
### BUGGY CODE ###

import bisect

N = int(input())

largest = []
for i in range(N):
    A_i = int(input())
    idx = bisect.bisect_left(largest, A_i)
    if idx == 0:
        largest.insert(0, A_i)
    else:
        largest[idx - 1] = A_i
print(len(largest))


### FIXED CODE ###

import bisect
from collections import deque

N = int(input())

largest = deque([])
for i in range(N):
    A_i = int(input())
    idx = bisect.bisect_left(largest, A_i)
    if idx == 0:
        largest.appendleft(A_i)
    else:
        largest[idx - 1] = A_i
print(len(largest))
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
maxim=0
ans=[]
for i in range(n-k+1):
    if maxim<=sum(p[i:i+k]):
        maxim=sum(p[i:i+k])
        ans=p[i:i+k]
ans1=(sum(ans)+k)/2

print(ans1)


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
maxim=[0]*(n-k+1)
cnt=0
s=0
for i in range(n):
    cnt+=1
    s+=p[i]
    if cnt==k:
        maxim[i-(k-1)]=s
        cnt=k-1
        s+=-p[i-(k-1)]

ans=(max(maxim)+k)/2
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())

import numpy as np
from scipy.sparse.csgraph import shortest_path

l = np.array([[float("inf") for i in range(n)] for j in range(n)])
ans = []
for _ in range(m):
   a,b,c = map(int,input().split())
   l[a-1][b-1] = c
   l[b-1][a-1] = c
   if a > b:
      ans.append((b,a))
   else:
      ans.append((a,b))

d, p = shortest_path(l, return_predecessors=True)


for pp in p:
   for idx, ppp in enumerate(pp):
      if idx < ppp:
         if (idx+1, ppp+1) in ans:
            ans.remove((idx+1, ppp+1))
      else:
         if (ppp+1, idx+1) in ans:
            ans.remove((ppp+1, idx+1))
print(len(ans))

### FIXED CODE ###

n,m = map(int,input().split())

import numpy as np
from scipy.sparse.csgraph import shortest_path

l = np.array([[float("inf") for i in range(n)] for j in range(n)])
from collections import defaultdict
ans = defaultdict(int)
for _ in range(m):
   a,b,c = map(int,input().split())
   l[a-1][b-1] = c
   l[b-1][a-1] = c
   if a > b:
      ans[(b,a)] = 1
   else:
      ans[(a,b)] = 1

d, p = shortest_path(l, return_predecessors=True)


for pp in p:
   for idx, ppp in enumerate(pp):
      if idx < ppp:
         ans[(idx+1,ppp+1)] = 0
      else:
         ans[(ppp+1,idx+1)] = 0
print(sum(ans.values()))
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

"""
H Wの後に
#.#.
###.
みたいな文字列を受け取る
"""
H,W = map(int,input().split(' '))
MAP = [['#']*(W+1)] + [None]*H

for i in range(1,H+1):
    MAP[i] = ['#'] + list(map(str,input()))
import queue
q = queue.Queue()


MAP[H][W] = 'G'
visited = [None]*(H+1)
for i in range(H+1):
    visited[i] = [False]*(W+1)

d_num = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if MAP[i][j]=='#':
            d_num += 1

def is_okay(x,y):
    if not (0<x<W+1) or not (0<y<H+1):
        return False
    if visited[y][x] or MAP[y][x]=='#':
        return False
    return True

n = 0
q.put([1,1,n])
ans = 10**7 + 7

while not q.empty():
    x,y,n = q.get()
    k = MAP[y][x]

    n += 1
    if k=='G':
        ans = min(ans,n)
        continue

    if is_okay(x+1,y): q.put([x+1,y,n])
    if is_okay(x-1,y): q.put([x-1,y,n])
    if is_okay(x,y+1): q.put([x,y+1,n])
    if is_okay(x,y-1): q.put([x,y-1,n])
    visited[y][x] = True

if not ans==10**7 + 7:
    ANS = H*W - ans - d_num
else:
    ANS = -1

print(ANS)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

"""
H Wの後に
#.#.
###.
みたいな文字列を受け取る
"""
H,W = map(int,input().split(' '))
MAP = [['#']*(W+1)] + [None]*H

for i in range(1,H+1):
    MAP[i] = ['#'] + list(map(str,input()))
import queue
q = queue.Queue()


MAP[H][W] = 'G'
visited = [None]*(H+1)
for i in range(H+1):
    visited[i] = [False]*(W+1)

d_num = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if MAP[i][j]=='#':
            d_num += 1

def is_okay(x,y):
    if not (0<x<W+1) or not (0<y<H+1):
        return False
    if visited[y][x] or MAP[y][x]=='#':
        return False
    return True

n = 0
q.put([1,1,n])
ans = 10**7 + 7

while not q.empty():
    x,y,n = q.get()
    k = MAP[y][x]

    n += 1
    if k=='G':
        ans = min(ans,n)
        break

    if is_okay(x+1,y):
        q.put([x+1,y,n])
        visited[y][x+1] = True
    if is_okay(x-1,y):
        q.put([x-1,y,n])
        visited[y][x-1] = True
    if is_okay(x,y+1):
        q.put([x,y+1,n])
        visited[y+1][x] = True
    if is_okay(x,y-1):
        q.put([x,y-1,n])
        visited[y-1][x] = True


if not ans==10**7 + 7:
    ANS = H*W - ans - d_num
else:
    ANS = -1

print(ANS)
### BUGGY CODE ###

from itertools import permutations
n=int(input())
N=list(map(int,input().split()))
ans=[]
for i in list(permutations(N)):
    if 1 in ans:break
    flag=1
    i=list(i)
    i.insert(0,i[-1])
    i.append(i[1])
    for j in range(1,n):
        if i[j]!=i[j-1]^i[j+1]:
            flag=0
            break
    ans.append(flag)
if 1 in ans:print("Yes")
else:print("No")

### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
temp = 0
for i in A:
    temp = temp ^ i
if(temp == 0):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

B = [float('inf')]*(10 ** 5)
A = [float('inf')]*(10 ** 5)
def main():
    accum = 0
    cost = 0
    N, M = map(int, input().split())
    for i in range(N):
        A[i], B[i] = map(int, input().split())
    while accum < M:
         index = A.index(min(A))
         Aind = A.pop(index)
         Bind = B.pop(index)
         if accum + Bind > M:
             cost += Aind * (M - accum)
             accum = M
         else:
             accum += Bind
             cost += Aind * Bind
    print(cost)

main()


### FIXED CODE ###

from operator import itemgetter
A = []

def main():
    accum = 0
    cost = 0
    N, M = map(int, input().split())
    for i in range(N):
        A.append(list(map(int, input().split())))
    B = sorted(A, key = itemgetter(0))
    while accum < M:
         eB = B.pop(0)
         if accum + eB[1] > M:
             cost += eB[0] * (M - accum)
             accum = M
         else:
             accum += eB[1]
             cost += eB[0] * eB[1]
    print(cost)

main()
### BUGGY CODE ###

import math
import copy

def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l

n=nCast(input())
a=nCast(inputArr1(n))
b=copy.deepcopy(a)





def akey(a):
    return a[0],a[1]
def bkey(a):
    return a[1],a[0]
list.sort(a,key=akey,reverse=True)
list.sort(b,key=bkey,reverse=True)

def remove(a, data,tag):
    if tag:
        tag=0
    else:
        tag=1
    n = len(a)
    first = 0
    last = n - 1

    while first <= last:
        mid = int(first + ((last - first) / 2))

        if a[mid][tag] < data[tag] or (a[mid][tag] == data[tag] and a[mid][1-tag] < data[1-tag]):
            last = mid - 1
        elif a[mid][tag] > data[tag] or (a[mid][tag] == data[tag] and a[mid][1-tag] > data[1-tag]):
            first = mid + 1
        else:
            del a[mid]
            return

def func(a,b):
    pa,pb=0,0
    tag=True
    while len(a)!=0:

        if a[0]==b[0]:
            tmp=a[0]
        else:
            v1=a[0][0]-b[0][1]
            v2=b[0][0]-b[1][1]
            if v1>v2:
                tmp=a[0]
            else:
                tmp=b[0]
        if tag:
            pa+=tmp[0]
        else:
            pb+=tmp[1]
        remove(a,tmp,tag)
        remove(b,tmp,not tag)
        tag=not tag
        a,b=b,a

    return pa-pb
    
print(func(a,b)) 







### FIXED CODE ###

import math
import copy

def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l

n=nCast(input())
a=nCast(inputArr1(n))

def akey(a):
    return a[0]+a[1]
list.sort(a,key=akey,reverse=True)


def func(a):
    pa,pb=0,0
    tag=True
    for idx in range(0,len(a)):
        if tag:
            pa+=a[idx][0]
        else:
            pb+=a[idx][1]
        tag=not tag
    return pa-pb
    
print(func(a))
### BUGGY CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

R,G,B,N =[int(x) for x in input().split()]
count = 0
for i in range(N//R +2):
    for j in range(N//G +2):
        for k in range(N//B +2):
            
            if i*R+j*G+k*B == N:
                count += 1

print(count)

### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

R,G,B,N =[int(x) for x in input().split()]
a = 0
for i in range(N//R+1):
    for j in range(((N-(i*R))//G)+1):
        if (N -i*R-j*G)%B == 0:
            a += 1
                       
           

print(a)
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
s=0
for a in range(K):
    for b in range(K):
        for c in range(K):
            s+=gcd(a+1,b+1,c+1)
            #print(s)
print(s)

### FIXED CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
s=0
q=0
w=0
e=0
for i in range(K):
    q+=gcd(i+1,i+1,i+1)
    
for a in range(K):
    for b in range(K):
        if not a==b:
            w+=3*gcd(a+1,a+1,b+1)
for a in range(1,K-1):
    #print(a)
    for b in range(a+1,K):
     #   print(b)
        for c in range(b+1,K+1):
      #      print(c)
            e+=6*gcd(a,b,c)
#print(q,w,e)     
print(q+w+e)
### BUGGY CODE ###

N=int(input())
G=[[] for _ in range(N)]
di=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w])
    G[v-1].append([u-1,w])

di[0]=0

for i in range(N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=[[i,0]]
    while stack:
        x,d=stack.pop()
        for g,dis in G[x]:
            if di[g]!=-1:
                di[i]=(di[g]+d+dis)%2
                break
            if seen[g]==0:
                stack.append([g,d+dis])
                seen[g]=1

for i in range(N):
    print(di[i]%2)




### FIXED CODE ###


from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w])
    G[v-1].append([u-1,w])

di[0]=0
for g,w in G[0]:
    di[g]=w

for i in range(1,N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=copy(G[0])
    seen[0]=1
    dis=0
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        if y==i:
            di[i]=dis+d
            break
        else:
            for z,dist in G[y]:
                if seen[z]==0:
                    di[z]=dis+d+dist
                    stack.append([z,dis+d+dist])

for i in range(N):
    if di[i]%2==0:
        print(0)
    else:
        print(1)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.reverse()
ans = []
nC2 = n * (n - 1) // 2

uf = UnionFind(n)
for a, b in ab:
    c = nC2
    for v in uf.parents:
        if v < -1:
            c -= v * (v + 1) // 2
    ans.append(c)
    uf.union(a-1, b-1)

ans.reverse()

for ai in ans:
    print(ai)


### FIXED CODE ###

def xC2(x):
    if x == 1:
        return 0
    else:
        return x * (x-1) // 2

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return 0

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        nx, ny = - self.parents[x],  - self.parents[y]

        self.parents[x] += self.parents[y]
        self.parents[y] = x

        return xC2(nx + ny) - xC2(nx) - xC2(ny)

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.reverse()
ans = [xC2(n)]

uf = UnionFind(n)
for a, b in ab:
    ans.append(ans[-1] - uf.union(a-1, b-1))

ans.reverse()

for ai in ans[1:]:
    print(ai)
### BUGGY CODE ###

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    frd=[[] for i in range(n)]
    #print(frd)
    for i in range(m):
        a,b=INTM()
        for k in range(n):
            if ((a in frd[k])or(b in frd[k])):
                if not(a in frd[k]):
                    frd[k].append(a)
                if not(b in frd[k]):
                    frd[k].append(b)
                break
            elif frd[k]==[]:
                frd[k].append(a)
                frd[k].append(b)
    
    ans=1
    for i in range(n):
        ans=max(ans,len(frd[i]))
    
    print(ans)

                
if __name__=='__main__':
    do()

### FIXED CODE ###

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def do():
    n,m=INTM()
    uf=UnionFind(n)
    for i in range(m):
        a,b=INTM()
        uf.union(a-1,b-1)

    ans=0

    for i in range(n):
        ans=max(ans,uf.size(i))
    
    print(ans)
                
if __name__=='__main__':
    do()
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()

lr = [list(map(int,input().split())) for _ in range(Q)]

#print(N,Q,S)
#print(lr)

#print(S[0:5])

for _ in range(Q):
    l = lr[_][0]
    r = lr[_][1]
    #print(_,S[0:r],S[0:(l-1)])
    #print(S[0:r].count('AC')-S[0:l].count('AC'))
    #print(_,S[l-1:r])
    print(S[l-1:r].count('AC'))


### FIXED CODE ###

N,Q = map(int,input().split())
S = input()

lr = [list(map(int,input().split())) for _ in range(Q)]

#print(N,Q,S)
#print(lr)

#print(S[0:5])

CC=[0]
for _ in range(1,N):
    if (S[_-1:_+1] == 'AC'):
        CC.append(CC[_-1]+1)
    else:
        CC.append(CC[_-1])

    #CC.append(S[0:_].count('AC'))

#print(CC)

for _ in range(Q):
    l = lr[_][0]
    r = lr[_][1]

    print(CC[r-1]-CC[l-1])

#for _ in range(Q):
#    l = lr[_][0]
#    r = lr[_][1]
    #print(_,S[0:r],S[0:(l-1)])
    #print(S[0:r].count('AC')-S[0:l].count('AC'))
    #print(_,S[l-1:r])
#    print(S[l-1:r].count('AC'))
### BUGGY CODE ###

s = input()
mod = 10**9+7
dp = [[0]*13 for i in range(len(s))]
if s[0] != '?':
  dp[0][int(s[0])] = 1
else:
  for i in range(10):
    dp[0][i] = 1
for i in range(1,len(s)):
  if s[i] != '?':
    for j in range(13):
      t = (j*10+int(s[i]))%13
      dp[i][t] += dp[i-1][j]
      dp[i][t] = dp[i][t]%mod
  else:
    for k in range(10):
      for j in range(13):
        t = (j*10+k)%13
        dp[i][t] += dp[i-1][j]
        dp[i][t] = dp[i][t]%mod
print(dp[len(s)-1][5]%mod)

### FIXED CODE ###

s = input()
mod = 10**9+7
dp = [[0]*13 for i in range(len(s))]
if s[0] != '?':
  dp[0][int(s[0])] = 1
else:
  for i in range(10):
    dp[0][i] = 1
for i in range(1,len(s)):
  if s[i] != '?':
    for j in range(13):
      t = (j*10+int(s[i]))%13
      dp[i][t] += dp[i-1][j]
      dp[i][t] = dp[i][t]%mod
  else:
    for k in range(10):
      for j in range(13):
        t = (j*10+k)%13
        dp[i][t] += dp[i-1][j]
        dp[i][t] = dp[i][t]%mod
print(dp[len(s)-1][5]%mod)
### BUGGY CODE ###

N = int(input())
card = [int(i) for i in input().split()]
s = sum(card)
min_sum = [abs(s - 2*sum(card[0:i])) for i in range(1, N)]
print(min(min_sum))

### FIXED CODE ###

N = int(input())
card = list(map(int, input().split()))
s = sum(card)
p_sum = 0
min_sum = []
for i in card[:-1]:
    p_sum += i
    min_sum.append(abs(s- 2 * p_sum))
print(min(min_sum))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
MOD = 10 ** 9 + 7
one = [0] * 60

for num in A:
    for digit in range(60):
        one[digit] += num >> digit & 1

for digit in range(60):
    ans += (one[digit] * (N - one[digit]) * pow(2, digit, MOD)) % MOD
    ans %= MOD

print(ans)


### FIXED CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
ans = 0
MOD = 10 ** 9 + 7

for digit in range(60):
    one = np.count_nonzero((A >> digit) & 1)
    ans += (one * (N - one) * pow(2, digit, MOD)) % MOD
    ans %= MOD

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

nk = input().split()
seisuuretu = input().split()

for i in range(len(seisuuretu)):
    seisuuretu[i] = int(seisuuretu[i])

list_max = set()
beautiful_list = []
for start in range(len(seisuuretu) + 1):
    for end in range(len(seisuuretu) + 1):
        if start < end:
            temp_pattern = bin(sum(seisuuretu[start:end]))[2:]
            beautiful_list.append(temp_pattern)
            list_max |= {len(temp_pattern),}

list_max = -max(list_max)

status = True
while status == True:
    temp = []
    count = 0
    len_all = 0
    for i in beautiful_list:
        try:
            if int(i[list_max]) == 1:
                count += 1
                temp.append(i)
        except:
            continue
    if count > int(nk[1]):
        list_max += 1
        beautiful_list = temp
    elif count == int(nk[1]):
        beautiful_list = temp
        num_count = True
        for num in beautiful_list:
            if num_count == True:
                ronriseki = int(num, 2)
            else:
                ronriseki = ronriseki & int(num, 2)
            num_count = False
        print(ronriseki)
        status = False
    elif list_max == -1:
        num_count = True
        for num in beautiful_list:
            if num_count == True:
                ronriseki = int(num, 2)
            else:
                ronriseki = ronriseki & int(num, 2)
            num_count = False
        print(ronriseki)
        status = False
    else:
        list_max += 1


### FIXED CODE ###

nk = input().split()
seisuuretu_2 = input().split()
nk1 = int(nk[1])

#seisuuretu = [int(i) for i in seisuuretu_2]
seisuuretu = list(map(int, seisuuretu_2))

list_max = set()
beautiful_list = []
for start in range(len(seisuuretu) + 1):
    for end in range(len(seisuuretu) + 1):
        if start < end:
            temp_pattern = bin(sum(seisuuretu[start:end]))[2:]
            beautiful_list.append(temp_pattern)
            list_max |= {len(temp_pattern),}

list_max = -max(list_max)

status = True
while status == True:
    temp = []
    count = 0
    for i in beautiful_list:
        try:
            if i[list_max] == "1":
                count += 1
                temp.append(i)
        except:
            continue
    if count > nk1:
        list_max += 1
        beautiful_list = temp
    elif count == nk1:
        num_count = True
        for num in temp:
            if num_count == True:
                ronriseki = int(num, 2)
            else:
                ronriseki = ronriseki & int(num, 2)
            num_count = False
        print(ronriseki)
        exit()
        status = False
    elif list_max == -1:
        num_count = True
        for num in beautiful_list:
            if num_count == True:
                ronriseki = int(num, 2)
            else:
                ronriseki = ronriseki & int(num, 2)
            num_count = False
        print(ronriseki)
        exit()
        status = False
    else:
        list_max += 1
### BUGGY CODE ###

import copy
s = input()
n = len(s)
mod = 10**9+7

moji = [[0,0,0,0] for _ in range(n+1)]

for i in range(1,n+1):
    moji[i] = copy.deepcopy(moji[i-1])
    if s[i-1] == 'A':
        moji[i][0] += 1
    if s[i-1] == 'B':
        moji[i][1] += 1
    if s[i-1] == 'C':
        moji[i][2] += 1
    if s[i-1] == '?':
        moji[i][3] += 1

ans = 0
for i in range(n):
    al,cr,hl,hr = moji[i][0], moji[n][2]-moji[i+1][2], moji[i][3], moji[n][3]-moji[i+1][3]
    if s[i] == 'B' or s[i] == '?':
        ans += (al*3 + hl) * (cr*3 + hr) * 3**(hr+hl-2)
    ans %= mod
print(int(ans))


### FIXED CODE ###

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

moji = [[0,0,0,0] for _ in range(n+1)]

for i in range(1,n+1):
    for k in range(4):
        moji[i][k] += moji[i-1][k]
    if s[i-1] == 'A':
        moji[i][0] += 1
        continue
    elif s[i-1] == 'B':
        moji[i][1] += 1
        continue
    elif s[i-1] == 'C':
        moji[i][2] += 1
        continue
    else:
        moji[i][3] += 1

h = s.count('?')
mt = [1]
for i in range(h+1):
    mt.append(mt[-1]*3 % mod)
mt += [1/9,1/3]
ans = 0
for i in range(n):
    al,cr,hl,hr = moji[i][0], moji[n][2]-moji[i+1][2], moji[i][3], moji[n][3]-moji[i+1][3]
    if s[i] == 'B' or s[i] == '?':
        k = (al*3 + hl) * (cr*3 + hr) * mt[hr+hl-2]
        ans += int(k) % mod
print(ans%mod)
### BUGGY CODE ###

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

tuples = [p[i:i+K] for i in range (N-(K-1))]
m = max(map(sum,tuples))

print((m+K)/2)

### FIXED CODE ###

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

s = sum(p[:K]) 
m = s

for i in range(N-K):
    s = s - p[i] + p[K+i]
    if m < s:
        m = s

print((m+K)/2)