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

import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

L = [[int(v) for v in input().split()] for _ in range(M * 2)]

ans = 10 ** 18
for i in range(1 << M):
    a = []
    for j in range(M):
        if (i >> j) & 1:
            a.append(j)

    s = set()
    p = 0
    for v in a:
        s = s | set(L[v * 2 + 1])
        p += L[v * 2][0]

    if len(s) != N:
        continue

    ans = min(ans, p)

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

### FIXED CODE ###

import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

L = []
v = 0
for _ in range(M):
    a, b = map(int, input().split())
    l = sum([1 << (int(v) - 1) for v in input().split()])
    L.append([a, b, l])
    v = v | l
if v != (1 << N) - 1:
     print(-1)
     exit()

dp = [[10 ** 18 for _ in range(1 << N)] for _ in range(M + 1)]
dp[0][0] = 0

for i in range(M):
     for j in range(1 << N):
          dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

          dp[i + 1][j | L[i][2]] =  min(dp[i + 1][j | L[i][2]], dp[i][j] + L[i][0])

print(dp[M][(1 << N) - 1])
### BUGGY CODE ###

from itertools import combinations

N = int(input())
A = [int(n) for n in input().split()]
print(sum([i*j for i,j in combinations(A, 2)])%(10**9+7))

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
mod = 10**9 + 7
sum_A = sum(A)
ans = 0
for i in A:
  ans += i * (sum_A := sum_A - i) % mod
  
print(ans % mod)
### BUGGY CODE ###

def main():
  
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  
  dp=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag[0][0][0]=True
  
  def memorize(f):
    table={}
    def func(*args):
        if not args in table:
            table[args]=f(*args)
        return table[args]
    return func

  @memorize
  def sushi(c1,c2,c3):    
    if flag[c1][c2][c3]:
      return dp[c1][c2][c3]
    else:
      flag[c1][c2][c3]=True
      tmp=c1+c2+c3
      ans=n/tmp
      if c1>0:
        ans+=c1*sushi(c1-1,c2,c3)/tmp
      if c2>0:
        ans+=c2*sushi(c1+1,c2-1,c3)/tmp
      if c3>0:
        ans+=c3*sushi(c1,c2+1,c3-1)/tmp
      dp[c1][c2][c3]=ans  
      return ans

  #print(dp) 
  print(sushi(c1,c2,c3))      
if __name__=='__main__':
  main()
        

### FIXED CODE ###

def main():
  
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  a=c1+c2+c3+1
  b=c2+c3+1
  c=c3+1
  
  dp=[[[0]*a for _ in range(b)] for _ in  range(c)]
  
  for i in range(c):
    for j in range(b-i):
      for k in range(a-i-j):
        tmp=i+j+k
        if tmp==0:
          continue
        else:
          dp[i][j][k]=n/tmp
          if i>0:
            dp[i][j][k]+=i*dp[i-1][j+1][k]/tmp
          if j>0:
            dp[i][j][k]+=j*dp[i][j-1][k+1]/tmp
          if k>0:
            dp[i][j][k]+=k*dp[i][j][k-1]/tmp
  print(dp[c3][c2][c1])
             
if __name__=='__main__':
  main()
### BUGGY CODE ###

import sys
from bisect import bisect_left
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
lst = list(readline().split())
mul = 1
for _ in lst :
  x = int(_)
  if(mul>10**18):
    mul = -1
    continue
  mul*=x

if mul> 10**18 :
  mul = -1

print(mul)


### FIXED CODE ###

import sys
from bisect import bisect_left
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
lst = list(map(int, readline().split()))
lst.sort()
lst.reverse()
mul = 1
if 0 in lst : 
  print(0)
else :
  for x in lst :
 #   print(x,mul)
    if(mul>10**18):
      mul = -1
      break
    mul*=x

  if mul> 10**18 :
    mul = -1

  print(mul)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
n, k = map(int, input().split())
s = list(map(int, input()))

# Run Length Encoding
rle = list()
target = 1
count = 0
for i in range(n):
    if s[i] == target:
        count += 1
    else:
        target = 1 - target
        rle.append(count)
        count = 1
rle.append(count)
if target == 0:
    rle.append(0)

offset = 2 * k + 1
res = 0

# two pointers
for i in range(0, len(rle), 2):
    left = i
    right = min(i + offset, len(rle))
    cand = 0
    for j in range(left, right):
        cand += rle[j]
    res = max(res, cand)

print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, k = map(int, input().split())
s = list(map(int, input()))

# Run Length Encoding
rle = list()
target = 1
count = 0
for i in range(n):
    if s[i] == target:
        count += 1
    else:
        target = 1 - target
        rle.append(count)
        count = 1
rle.append(count)
if target == 0:
    rle.append(0)

offset = 2 * k + 1
res = 0

# two pointers
left = 0
right = 0
cand = 0
for i in range(0, len(rle), 2):
    next_left = i
    next_right = min(i + offset, len(rle))

    while(next_left > left):
        cand -= rle[left]
        left += 1

    while(next_right > right):
        cand += rle[right]
        right += 1

    res = max(res, cand)

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

import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :10**30)
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					#self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append([q-1 + t * n, 0])
	edges[q-1 + t * n].append([p-1 + t * n, 0])
	if len(edges[p-1 + t * n]) == 1:
		edges[p-1 + t * n].append([p-1 + 0 * n, 0])
		edges[p-1 + 0 * n].append([p-1 + t * n, 1])
	if len(edges[q-1 + t * n]) == 1:
		edges[q-1 + t * n].append([q-1 + 0 * n, 0])
		edges[q-1 + 0 * n].append([q-1 + t * n, 1])

d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res > 10**20:
	print(-1)
else:
	print(res)

### FIXED CODE ###

import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :10**30)
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					#self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append((q-1 + t * n, 0))
	edges[q-1 + t * n].append((p-1 + t * n, 0))
	if len(edges[p-1 + t * n]) == 1:
		edges[p-1 + t * n].append((p-1 + 0 * n, 0))
		edges[p-1 + 0 * n].append((p-1 + t * n, 1))
	if len(edges[q-1 + t * n]) == 1:
		edges[q-1 + t * n].append((q-1 + 0 * n, 0))
		edges[q-1 + 0 * n].append((q-1 + t * n, 1))

d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res > 10**20:
	print(-1)
else:
	print(res)
### BUGGY CODE ###

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

# estP = [-1]
def est(i):
    return 1.0 + (i - 1) * 0.5
# for i in range(1, 1001):
# print(i, sum([j * 1.0 / i for j in range(1, i + 1)]))
# estP.append(sum([j * 1.0 / i for j in range(1, i + 1)]))
# print(i, 1.0 + (i - 1) * 0.5)
# # print(estP)

m = -1.0
for i in range(N - K + 1):
    vi = sum([est(P[j]) for j in range(i, i + K)])
    m = max(vi, m)
print(m)

### FIXED CODE ###

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

# estP = [-1]
def est(i):
    return 1.0 + (i - 1) * 0.5
# for i in range(1, 1001):
# print(i, sum([j * 1.0 / i for j in range(1, i + 1)]))
# estP.append(sum([j * 1.0 / i for j in range(1, i + 1)]))
# print(i, 1.0 + (i - 1) * 0.5)
# # print(estP)

# 普通に計算する
# - 2x10e5 の2重ループなのでTLE

# m = -1.0
# for i in range(N - K + 1):
#     vi = sum([est(P[j]) for j in range(i, i + K)])
#     m = max(vi, m)
# print(m)


# かしこい計算: 累積和
# WAになってしまった
# sumA = [est(P[0])]
# for i in range(1, N):
#     sumA.append(sumA[-1] + est(P[i]))
# # print([est(P[i]) for i in range(N)])
# # print(sumA)

# m = -1
# for i in range(N - K):
#     # print(i, i + K, sumA[i + K] - sumA[i])
#     m = max(m, sumA[i + K] - sumA[i])
# print(m)

expected = [(P[i] + 1) / 2 for i in range(N)]
# print(expected)
# print(expected[:K])

# 0 ~ K-1 の期待値
ans = sum(expected[:K])
tmp = ans
for i in range(N - K):
    # 新しく追加 (i番目を抜いて，i+K番目を入れる，横に移動)
    tmp = tmp + expected[i + K] - expected[i]
    ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n, k = map(int, input().split())
a = list(map(int, input().split()))
rui = [1]
t = 1
for i in range(n):
    t *= a[i]
    rui += [t]

for i in range(n+1):
    if i < k+1: continue
    # print(i, rui[i] / rui[i - k])
    # print(i-1, rui[i - 1] / rui[i - k - 1])
    if rui[i] / rui[i - k] > rui[i - 1] / rui[i - k - 1] :
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k, n):
    if a[i] > a[i - k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import Counter

N = int(input())
A_array = list(map(int, input().split()))
Ai_dict = Counter(A_array)


def calc_comb(Ai, dictionary):
    num = 0
    for k,v in dictionary.items():
        if k == Ai:
            N_Ai = v -1 #1こ抜いた数. 
        else:
            N_Ai = v
        num += N_Ai*(N_Ai-1)/2
    return int(num)


res_dict = dict([])

for n in A_array:
    if not n in res_dict.keys():
        res_dict[n] = calc_comb(n, Ai_dict)
        print(calc_comb(n, Ai_dict))
    else:
        print(res_dict[n])


### FIXED CODE ###

from collections import Counter

N = int(input())
A_array = list(map(int, input().split()))
Ai_dict = Counter(A_array)


def calc_comb(dct):
    num = 0
    for k,v in dct.items():
        num += v*(v-1)/2
    return int(num)


res_dict = dict([])
TotalComb = calc_comb(Ai_dict)

for n in A_array:
    if not n in res_dict.keys():
        res_dict[n] = TotalComb - Ai_dict[n]+1
    print(res_dict[n])
### BUGGY CODE ###

import bisect

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()


count = 0

for i in range(n):
    x = a[i] + 1
    index1 = bisect.bisect_left(b, x)
    b_tmp = b[index1:]
    for j in b_tmp:
        y = j + 1
        index2 = bisect.bisect_left(c, y)
        c_tmp = c[index2:]
        count += len(c_tmp)


print(count)

### FIXED CODE ###

import bisect

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()

count = 0

for i in b:
    x = bisect.bisect_left(a, i)
    y = bisect.bisect_right(c, i)
    count += x * (len(c) - y)

print(count)
### BUGGY CODE ###

import collections
N = int(input())
A = collections.Counter(list(map(int, input().split())))
seihou = []
tyouhou = []
ans = 0

for i in A.keys():
    if A[i] >= 2:
        tyouhou = tyouhou+[i]
    if A[i] >= 4:
        seihou = seihou+[i]

if len(seihou) >= 1:
    ans = max(seihou)**2

if len(tyouhou) >= 2:
    tyouhou.sort()
    ans = max(ans, tyouhou[-1]*tyouhou[-2])
print(ans)

### FIXED CODE ###

import collections
N = int(input())
A = collections.Counter(list(map(int, input().split())))
seihou = []
tyouhou = []
ans = 0

for i in A.keys():
    if A[i] >= 2:
        tyouhou.append(i)
    if A[i] >= 4:
        seihou.append(i)

if len(seihou) >= 1:
    ans = max(seihou)**2

if len(tyouhou) >= 2:
    c = max(tyouhou)
    tyouhou.remove(c)
    ans = max(ans, c*max(tyouhou))
print(ans)
### BUGGY CODE ###

import copy

N = input()
data = input().split()
original = data.copy()
data2 = original.copy()

res_count = 0
loop_count = 0

for num in data:
    flag = 0
    data2 = original.copy()
    data2.pop(loop_count)
 #   print(original)
#    print(data2)
    for num2 in data2:
        if (int(num) % int(num2)) == 0:
            flag = 1
    
    if flag == 0:
        res_count += 1
 #       print('num = {}  num 2 = {}'.format(num,num2))

    loop_count += 1
    
print(res_count)

   




### FIXED CODE ###

from collections import Counter
import math

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

a.sort()

is_prime = [True]*(10**6 + 1)

is_prime[0] = False

maxA = max(a)

for i in set(a):
    for j in range(2 * i, maxA+1, i):
        is_prime[j] = False

result = 0
c = Counter(a)

for e in set(a):
        if is_prime[e] and c[e] == 1:
    #        print('e = {}'.format(e))
             result += 1

print(result)
### BUGGY CODE ###

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

dis = 0
done = [A[0]]
not_done = A[1:N]

while True:
    min_d = 1e6
    for a in done:
        for b in range(len(not_done)):
            if a>b:
                d = min(abs(a-not_done[b]), abs(a-not_done[b]-20))
            else:
                d = min(abs(a-not_done[b]), abs(a-not_done[b]+20))
            min_d = min(d, min_d)
            min_idx = b
    dis += min_d
    done.append(not_done.pop(b))
    if len(not_done) ==0:
        break
print(dis)


### FIXED CODE ###

import numpy as np

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

A.append(K+A[0])
l = 0
for i in range(N):
    l = max(l, A[i+1]-A[i])
print(K-l)
### BUGGY CODE ###

N,K = input().split()
H = input().split()

if N < K:
    times = int(N)
else:
    times = int(K)

H_i =[int(i) for i in H]

for i in range(times):
    H_i.remove(max(H_i))

print(sum(H_i))

### FIXED CODE ###

enemmyCountN,killerTimeK = map(int,input().split())
enemyHp = list(map(int,input().split()))

enemyHp.sort()

resultEnemyCount = enemmyCountN - killerTimeK
countNormal = 0

if killerTimeK >= enemmyCountN:
    print(0)

else:
    for i in range(resultEnemyCount):
        countNormal += enemyHp[i]
    print(countNormal)
### BUGGY CODE ###

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    ret = list(map(str, sys.stdin.readline().rstrip()))
    Q = int(sys.stdin.readline().rstrip())

    for q in range(Q):
        line = sys.stdin.readline().split()
        if line[0] == '1':
            ret.reverse()
        elif line[0] == '2' and line[1] == '1':
            ret.insert(0, line[2])
        else:
            ret.append(line[2])

    print("".join(ret))



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    ret = sys.stdin.readline().rstrip()
    Q = int(sys.stdin.readline().rstrip())
    m = ""
    u = ""
    r = 0
    for q in range(Q):
        line = sys.stdin.readline().split()
        if line[0] == '1':
            m, u = u, m
            r ^= 1
        elif line[0] == '2' and line[1] == '1':
            m += line[2]
        else:
            u += line[2]

    if r == 0:
        print(m[::-1] + ret[::1] + u)
    else:
        print(m[::-1] + ret[::-1] + u)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N =int(input())
s = list(sorted(input()) for i in range(N))
cnt = 0
for i in range(N):
    cnt+=(s[i+1:]).count(s[i])
print(cnt)

### FIXED CODE ###

import collections

N =int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(s)
cnt = 0
ans =0
for i in set(s):
    cnt = c[i]
    ans += cnt*(cnt-1)//2
print(ans)
### BUGGY CODE ###

def gcd(m, n):
    r = m % n
    return n if r == 0 else gcd(n, r)


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

if n == 2:
    print(max(A))
    exit()

GCD = []
for i in range(n):
    A2 = A[:i] + A[i + 1:]
    g = gcd(A2[0], A2[1])
    for j in range(2, n - 1):
        g = gcd(g, A2[j])
        if g == 1:
            break
    GCD.append(g)

print(max(GCD))


### FIXED CODE ###

def gcd(m, n):
    r = m % n
    return n if r == 0 else gcd(n, r)


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

GCD_left = A[:]
for i in range(1, n):
    GCD_left[i] = gcd(GCD_left[i - 1], GCD_left[i])
GCD_right = A[:]
for i in range(n - 2, -1, -1):
    GCD_right[i] = gcd(GCD_right[i], GCD_right[i + 1])

GCD = [1] * n
GCD[0], GCD[-1] = GCD_right[1], GCD_left[-2]
for i in range(1, n - 1):
    GCD[i] = gcd(GCD_left[i - 1], GCD_right[i + 1])

print(max(GCD))
### BUGGY CODE ###

from pprint import pprint
from collections import deque, defaultdict


def solve(n, q, edges, p):
    counter = defaultdict(int)

    parents = deque()
    # parents.append(0)
    # parents = []
    parents.append(0)
    visited = set()
    while parents:
        parent = parents.popleft()
        # parent = parents.pop()
        if parent in visited:
            continue
        visited.add(parent)
        counter[parent] += p[parent]
        # print("parent")
        # print(parent, counter[parent])
        for child in edges[parent]:
            if child in visited:
                continue
            # if counter[child] != 0:
            #    continue
            counter[child] = counter[parent]
            # print("child")
            # print(child, counter[child])
            parents.append(child)
            # parents.add(child)

    print(" ".join(list(map(str, counter.values()))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    edges = defaultdict(set)
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        # edges[a_i-1].append(b_i-1)
        # edges[b_i-1].append(a_i-1)
        edges[a_i-1].add(b_i-1)
        edges[b_i-1].add(a_i-1)

    p = defaultdict(int)
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p[p_i-1] += x_i

    solve(n, q, edges, p)

### FIXED CODE ###

from collections import deque


def solve(n, q, a, b, p, x):
    counter = [0] * n
    q_sum = [0] * n
    for i in range(q):
        q_sum[p[i]] += x[i]
    # pprint(q_sum)

    edges = {}
    for i in range(n-1):
        if a[i] not in edges:
            edges[a[i]] = []
        edges[a[i]].append(b[i])
    # pprint(edges)

    counter[0] = q_sum[0]
    children = deque()
    for child in edges[0]:
        counter[child] = q_sum[0]
        children.append(child)
    while children:
        child = children.popleft()
        counter[child] += q_sum[child]
        # print("child")
        # print(child, counter[child])
        if child in edges:
            for c in edges[child]:
                counter[c] = counter[child]
                # print("c")
                # print(c, counter[c])
                children.append(c)

    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    a = []
    b = []
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        a.append(a_i - 1)
        b.append(b_i - 1)

    p = []
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p.append(p_i-1)
        x.append(x_i)
    solve(n, q, a, b, p, x)
### BUGGY CODE ###

S=input()
N=len(S)
A=[0]*(N+1)
Q=[0]*(N+1)
AB=[0]*(N+1)
AQandQB=[0]*(N+1)
QQ=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  Q[i]=Q[i-1]
  if S[i-1] is "A":
    A[i]+=1
  elif S[i-1] is "?":
    Q[i]+=1
M=Q[N]
for i in range(1,N+1):
  AB[i]=AB[i-1]
  AQandQB[i]=AQandQB[i-1]
  QQ[i]=QQ[i-1]
  if S[i-1] is "B":
    AB[i]+=A[i-1]
    AQandQB[i]+=Q[i-1]
  elif S[i-1] is "?":
    AQandQB[i]+=A[i-1]
    QQ[i]+=Q[i-1]
for i in range(1,N+1):
  ABC[i-1]=ABC[i-1]%(10**9+7)
  ABC[i]=ABC[i-1]
  if S[i-1] is "C":
    ABC[i]+=AB[i-1]*(3**M)+(AQandQB[i-1])*(3**(M-1))+QQ[i-1]*(3**(M-2))
  elif S[i-1] is "?":
    ABC[i]+=AB[i-1]*(3**(M-1))+(AQandQB[i-1])*(3**(M-2))+QQ[i-1]*(3**(M-3))
print(int(ABC[N]%(10**9+7)))

### FIXED CODE ###

S=input()
N=len(S)
O=1
A=[0]*(N+1)
AB=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  AB[i]=AB[i-1]
  ABC[i]=ABC[i-1]
  if S[i-1] is "A":
    A[i]+=O
  elif S[i-1] is "B":
    AB[i]+=A[i-1]
  elif S[i-1] is "C":
    ABC[i]+=AB[i-1]
  elif S[i-1] is "?":
    A[i]*=3
    A[i]+=O
    AB[i]*=3
    AB[i]+=A[i-1]
    ABC[i]*=3
    ABC[i]+=AB[i-1]
    O*=3
  A[i]=A[i]%(10**9+7)
  AB[i]=AB[i]%(10**9+7)
  ABC[i]=ABC[i]%(10**9+7)
  O=O%(10**9+7)
print(int(ABC[N]%(10**9+7)))