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



from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    #nxt = defaultdict(set)
    nxt = defaultdict(list)

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

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j == 0:
                b = (l,h)
            else:
                before[(l,h)] += 1
                #nxt[b].add((l,h))
                nxt[b].append((l,h))
                b = (l,h)



    match_today = deque()
    checked = defaultdict(bool)
    for i in range(N):
        l,h = min(i+1, A[i][0]), max(i+1, A[i][0])
        #print(l,h, before[(l,h)])
        if before[(l,h)] == 0 and not checked[(l,h)]:
            match_today.append((l,h))
            checked[(l,h)] = True

    """
    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
    """
                

    
    ans = 0
    cnt_match = 0 
    while match_today:
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_today.append((nl, nh))
        
       


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

### FIXED CODE ###


from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    if next_opponent[b] == a:
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で戦う相手がaではないなら、順番が来るまで待つ
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
pre=a[0]
score=0
for i in range(1,n):
    score=pre*a[i]

    pre=score

if score>10**18:
    print(-1)
else:
    print(score)

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)

    if 0 in A:
        print('0')
        return
    prod=1
    for a in A:
        prod*=a
        if prod> 1000000000000000000:
            print('-1')
            return
    print(prod)

ans=main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
for _ in range(q):
  b,c=map(int,input().split())
  a=[c if x==b else x for x in a]
  print(sum(a))


### FIXED CODE ###

from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
num=defaultdict(int)
sm=0
for e in a:
    sm+=e
    num[e]+=1
q=int(input())
for _ in range(q):
  b,c=map(int,input().split())
  ans= sm+(c-b)*num[b]
  num[c]+=num[b]
  num[b]=0
  sm=ans
  print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
a = np.array( list(map(float, input().split(" "))) )
b = np.array( list(map(float, input().split(" "))) )
c = np.array( list(map(float, input().split(" "))) )

# a.sort()
# b.sort()
# c.sort()
dic = {}
def count_c(v):
    key = v
    if v in dic:
        return dic[v]
    else:
        val = len(np.where( (v < c) == True )[0])
        dic.update({key:val})
        return val

num = 0
for i in range(N):
    for j in range(N):
        if a[i] < b[j]:
            num += count_c(b[j])

print(num)

### FIXED CODE ###

N = int(input())
a = list(map(float, input().split(" ")))
b = list(map(float, input().split(" ")))
c = list(map(float, input().split(" ")))

a.sort()
c.sort()


def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

num = 0
for i in range(N):
    num += (bisect_left(a, b[i])) * (len(c) - bisect_right(c, b[i]))
print(num)
### BUGGY CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N = I()

def test(n):
    cnt = 0
    for i in range(1,100):
        for j in range(1,100):
            for k in range(1,100):
                if (i+j+k)**2 == n + (i*j + j*k + k*i):
                    cnt += 1 
                if (i+j+k)**2 - (i*j + j*k + k*i) > n*2:
                    break
    return cnt

for i in range(N):
    print(test(i+1))


### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N = I()

ans = [0 for _ in range(10050)]

for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
           v = (i+j+k)**2 - (i*j + j*k + k*i)
           if v < 10050:
            ans[v] += 1

for i in range(N):
    print(ans[i+1])
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
input=lambda :sys.stdin.readline().rstrip()
# inputs= sys.stdin.buffer.readlines
INF=float("inf")
MOD=10**9+7

#input = sys.stdin.buffer.readline
#sys.setrecursionlimit(2147483647)

#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra

#map(int,input().split())

def main():
	n=int(input())
	s=input()
	
	ans=0
	cnt=0
	
	
	for d in range(1,n):
		cnt=0
		for i in range(n-d):
			if s[i]==s[i+d]:
				cnt+=1
				ans = max(ans, min(cnt, d))
			else:
				cnt=0
	print(ans)
	
	
	
	
	

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
input=lambda :sys.stdin.readline().rstrip()
# inputs= sys.stdin.buffer.readlines
INF=float("inf")
MOD=10**9+7

#input = sys.stdin.buffer.readline
#sys.setrecursionlimit(2147483647)

#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra

#map(int,input().split())

def main():
	n=int(input())
	s=input()
	
	ans=0
	cnt=0
	
	
	for d in range(1,n):
		cnt=0
		for i in range(n-d):
			if s[i]==s[i+d]:
				cnt+=1
				ans = max(ans, min(cnt, d))
			else:
				cnt=0
	print(ans)
	
	
	
	
	

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

s=input()
cnt=0
for i in range(1,len(s)):
    for j in range(i+1,len(s)+1):
        number=s[i-1:j]
        if int(number)%2019==0:
            cnt+=1
print(cnt)

### FIXED CODE ###

s=input()[::-1]
mod=[0]*2019
mod[0]=1
x=1
num=0
ans=0

for t in s:
    num += int(t) * x
    num %= 2019
    x *= 10
    x %= 2019
    mod[num] +=1

for u in mod:
    ans += u*(u-1)//2

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

n, k = map(int, input().split())
alist = sorted(list(map(int, input().split())))
mod = 10**9 + 7

fact = [1]
i = 1
while i < n:
    fact.append(fact[i-1] * i)
    i += 1 

def comb_fac(n, k):
    return fact[n] // (fact[n-k] * fact[k])

amax = 0
i = n-1
while i >= k-1:
    amax += alist[i] * comb_fac(i, k-1)
    i -= 1

amin = 0
i = 0
while i <= n-k:
    amin += alist[i] * comb_fac(n-i-1, k-1)
    i += 1
print((amax - amin) % mod)

### FIXED CODE ###

n, k = map(int, input().split())
alist = sorted(map(int, input().split()))
mod = 10**9 + 7

def comb(n, r, p=mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
p = mod
N = n
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

amax = 0
amin = 0
i = 0
while i <= n-k:
    cnt = comb(n-i-1, k-1)
    amax += (alist[n-i-1] * cnt)%mod
    amin += (alist[i] * cnt)%mod
    i += 1

print((amax - amin) % mod)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    q = list(input().split())
    if q[0] == '1':
        S = S[::-1]
    else:
        if q[1] == '1':
            S = q[2] + S
        else:
            S += q[2]
print(S)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
S = input()
Q = int(input())
flag = True
f = ''
b = ''
for i in range(Q):
    q = list(input().split())
    if q[0] == '1':
        flag = not flag
    else:
        if flag:
            if q[1] == '1':
                f = q[2] + f
            else:
                b += q[2]
        else:
            if q[1] == '1':
                b += q[2]
            else:
                f = q[2] + f
S = f + S + b
if not flag:
    S = S[::-1]
print(S)
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())

from collections import defaultdict

MOD = 10**9 + 7
T = defaultdict(list)
R = defaultdict(list)
visited = [-1]*(N+1)
for i in range(N-1):
    x,y = map(int, input().split())
    # x,y = min(x,y), max(x,y)
    T[x] += [y]
    T[y] += [x]

# DP = defaultdict(lambda : 0 )
DP = [[0] * (N+1) for _ in range(2)]

root = 1
visited[root] = 1
node = root
from collections import deque
q = deque()
q.append(node)

# while q:
#     node = q.popleft()
#     # print("node: ,", node)
#     if all(visited[child]!=-1 for child in T[node]):
#         continue
#     for chnode in T[node]:
#         if visited[chnode] == -1:
#             R[node] += [chnode]
#             visited[chnode] = 1
#             q.append(chnode)


def dfs(c,n,oya):
    # if len(T[n]) == 0:
    #     DP[0][n] = 1
    #     DP[1][n] = 1
    #     return 1

    if c == 0:
        black = 1
        for child_n in T[n]:
            if child_n == oya:
                continue
            black *= dfs(1, child_n, n) % MOD
        DP[0][n] = black % MOD
        return black % MOD
    else:
        white = 1
        for child_n in T[n]:
            if child_n == oya:
                continue
            white *= dfs(0, child_n, n) + dfs(1, child_n,n) % MOD
        DP[1][n] = white % MOD
        return white % MOD

print( (dfs(0, 1, None) + dfs(1,1, None)) % MOD) 



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())
from collections import defaultdict
MOD = 10**9 + 7

# T = defaultdict(list)
T = [set() for _ in range(N+1)]
for i in range(N-1):
    x,y = map(int, input().split())
    # T[x] += [y]
    # T[y] += [x]
    T[x].add(y)
    T[y].add(x)

def dfs(n,oya):
    b,w = 1,1
    for child_n in T[n]:
        if child_n == oya:
            continue
        child_b, child_w = dfs(child_n, n)
        b *= child_w % MOD
        w *= (child_b+child_w)%MOD
    return b%MOD, w%MOD
print( sum(dfs(1,None)) % MOD)
### BUGGY CODE ###

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

ans = -float("inf")
for x in range(n):
    #print(a*((x+1)%b)//b)
    if a*((x+1)%b)//b > ans:
        ans = a*((x+1)%b)//b

#print("----------")
print(ans)

### FIXED CODE ###

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

if n < b-1:
    print(a*(n%b)//b)
else:
    print(a*((b-1)%b)//b)
### BUGGY CODE ###

n, m = map(int, input().split())
l = list(map(int, input().split()))
l.sort()

for i in range(m):
  b, c = map(int, input().split())
  l[:b] = [c if x < c else x for x in l[:b]]
  l.sort()

print(sum(l))

### FIXED CODE ###

n, m = map(int, input().split())
l = list(map(int, input().split()))
l.sort()

bc = [list(map(int, input().split())) for i in range(m)]
bc = sorted(bc, key=lambda x: x[1], reverse=True)
count = 0

for i in range(m):
  b, c = bc[i][0], bc[i][1]
  l += [c]*b
  count += b
  if count >= n:
    break

l.sort(reverse=True)
print(sum(l[:n]))
### BUGGY CODE ###

import copy
n = int(input())
a = list(map(int,input().split()))
b = copy.copy(a)
sum_a = []
sum_b = []
ans_a = 0
ans_b = 0
for i in range(n):
    if i%2==0:
        if sum(a[:i+1])>0:
            sum_a.append(sum(a[:i+1]))
            tmp = 0
        else:
            tmp = abs(sum(a[:i+1]))+1
            a[i] += tmp
            ans_a += tmp
            sum_a.append(sum(a[:i+1]))
    else:
        if sum(a[:i+1])<0:
            sum_a.append(sum(a[:i+1]))
            tmp = 0
        else:
            tmp = abs(sum(a[:i+1]))+1
            a[i] -= tmp
            ans_a += tmp
            sum_a.append(sum(a[:i+1]))
    if i%2==1:
        if sum(b[:i+1])>0:
            sum_b.append(sum(b[:i+1]))
            tmp = 0
        else:
            tmp = abs(sum(b[:i+1]))+1
            b[i] += tmp
            ans_b += tmp
            sum_b.append(sum(b[:i+1]))
    else:
        if sum(b[:i+1])<0:
            sum_b.append(sum(b[:i+1]))
            tmp = 0
        else:
            tmp = abs(sum(b[:i+1]))+1
            b[i] -= tmp
            ans_b += tmp
            sum_b.append(sum(b[:i+1]))

#print(a)
#print(sum_a)
print(min(ans_a,ans_b))

### FIXED CODE ###

import copy
n = int(input())
a = list(map(int,input().split()))
b = copy.copy(a)
ans_a = 0
ans_b = 0
sum_a = 0
sum_b = 0
for i in range(n):
    if i%2==0:
        if sum_a+a[i]>0:
            tmp = 0
        else:
            tmp = abs(sum_a+a[i])+1
            a[i] += tmp
            ans_a += tmp
    else:
        if sum_a+a[i]<0:
            tmp = 0
        else:
            tmp = abs(sum_a+a[i])+1
            a[i] -= tmp
            ans_a += tmp
    sum_a+=a[i]
    if i%2==1:
        if sum_b+b[i]>0:
            tmp = 0
        else:
            tmp = abs(sum_b+b[i])+1
            b[i] += tmp
            ans_b += tmp
    else:
        if sum_b+b[i]<0:
            tmp = 0
        else:
            tmp = abs(sum_b+b[i])+1
            b[i] -= tmp
            ans_b += tmp
    sum_b+=b[i]
#print(a)
#print(sum_a)
print(min(ans_a,ans_b))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split(" ")))
dp = dict()
mod = 10 ** 9 + 7

def f(i, ma, mi):
    if i == N:
        return 1
    if (i, ma, mi) in dp:
        return dp[(i, ma, mi)]
    if A[i] != ma and A[i] != mi and A[i] != i - ma - mi:
        dp[(i, ma, mi)] = 0
        return 0

    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == ma:
        ans += f(i + 1, ma + 1, mi)
    if A[i] == mi:
        if ma > mi + 1:
            ans += f(i + 1, ma, mi + 1)
        else:
            ans += f(i + 1, mi + 1, ma)
    if A[i] == i - ma - mi:
        ans += f(i + 1, ma, mi)

    dp[(i, ma, mi)] = ans % mod
    return dp[(i, ma, mi)]

print(f(0, 0, 0) % mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

N = int(input())
A = list(map(int, input().strip().split(" ")))
dp = {i: dict() for i in range(N)}
mod = 10 ** 9 + 7

def f(i, ma, mi):
    if i == N:
        return 1
    if (ma, mi) in dp[i]:
        return dp[i][(ma, mi)]
    if A[i] != ma and A[i] != mi and A[i] != i - ma - mi:
        dp[i][(ma, mi)] = 0
        return 0

    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == ma:
        ans += f(i + 1, ma + 1, mi)
    if A[i] == mi:
        if ma > mi + 1:
            ans += f(i + 1, ma, mi + 1)
        else:
            ans += f(i + 1, mi + 1, ma)
    if A[i] == i - ma - mi:
        ans += f(i + 1, ma, mi)

    dp[i][(ma, mi)] = ans % mod
    return ans % mod

print(f(0, 0, 0) % mod)
### BUGGY CODE ###

def gcd(a,b):
    a,b=max(a,b),min(a,b)
    while b>0:
        a,b=b,a%b
    return(a)

k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += gcd(i,gcd(j,k))
print(ans)

### FIXED CODE ###

import math
ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += math.gcd(i,math.gcd(j,k))
print(ans)
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))

a = [e for e in a if e < k]
n = len(a)

dp = np.zeros((n + 1, k), bool)
dp[0][0] = True
for i, e in enumerate(a, 1):
    dp[i] = dp[i-1]
    dp[i, e:] |= dp[i-1, :-e]

dp2 = np.zeros((n + 1, k), bool)
dp2[0][0] = True
for i, e in enumerate(a[::-1], 1):
    dp2[i] = dp2[i-1]
    dp2[i, e:] |= dp2[i-1, :-e]

ans = 0
for i, e in enumerate(a, 1):
    li = [j for j in range(k) if dp[i-1][j]]
    li2 = [j for j in range(k) if dp2[n-i][j]]

    j = len(li2) - 1
    mx = 0
    for e2 in li:
        while j > 0 and e2 + li2[j] >= k:
            j -= 1

        if e2 + li2[j] < k:
            mx = max(mx, e2 + li2[j])

    if mx + e < k:
        ans += 1

print(ans)


### FIXED CODE ###

import numpy as np


def check(x):
    dp = np.zeros(k, np.bool)
    dp[0] = True
    for e in a[:x] + a[x+1:]:
        dp[e:] |= dp[:-e]

    return dp[-a[x]:].any()


n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

lb = -1
ub = n
while ub - lb > 1:
    m = (lb + ub) // 2
    if check(m):
        ub = m
    else:
        lb = m

print(ub)
### BUGGY CODE ###

N, a, b = map(int,input().split())
mod = 10**9+7

def prepare(n, mod):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= mod
        factorials.append(f)
    inv = pow(f, mod - 2, mod)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= mod
        invs[m - 1] = inv
    return factorials, invs

factorials, invs = prepare(N,mod)
sum = 1
for i in range(N) :
    sum = (sum * 2) % mod

nCa = (factorials[N] * invs[N-a] % mod * invs[a] % mod)
nCb = (factorials[N] * invs[N-b] % mod * invs[b] % mod)

sum = (sum - nCa - nCb - 1) % mod
print(sum)


### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10**9 + 7

def comb(n, r, mod):
    X = 1
    Y = 1
    for i in range(1,r+1):
        X = (X*(n-i+1))%mod
        Y = (Y*i)%mod
    return (X*pow(Y, mod-2, mod))%mod

ans = (pow(2, n, mod) -1 - comb(n, a, mod) - comb(n, b, mod))%mod
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
ab = []
for _ in range(m):
    a=int(input())
    ab.append(a)

dp = [0]*(n+1)
dp[0] = 1

for i in range(1, n+1):
    dp[i] = (dp[i-1] + dp[i-2])%1000000007
    if i in ab:
        dp[i] = 0

print(dp[-1])

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
 
dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
    if i in a:
        dp[i] = 0
print(dp[N])
### BUGGY CODE ###

S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

for i in range(1,len(S)-1):
    if S[i] == "A":
        leftA += 1
    elif S[i] == "C":
        rightC -= 1
    elif S[i] == "B":
        if leftQ >= 1:
            leftpatt = leftA * (3 ** leftQ) + leftQ * (3 ** (leftQ - 1))
        else:
            leftpatt = leftA
        if rightQ >= 1:
            rightpatt = rightC * (3 ** rightQ) + rightQ * (3 ** (rightQ - 1))
        else:
            rightpatt = rightC
        count += (leftpatt * rightpatt) % mod
        count %= mod
    else:
        rightQ -= 1
        if leftQ >= 1:
            leftpatt = leftA * (3 ** leftQ) + leftQ * (3 ** (leftQ - 1))
        else:
            leftpatt = leftA
        if rightQ >= 1:
            rightpatt = rightC * (3 ** rightQ) + rightQ * (3 ** (rightQ - 1))
        else:
            rightpatt = rightC
        leftQ += 1
        count += (leftpatt * rightpatt) % mod
        count %= mod
print(int(count))

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

def mult(a, b, mod):
    if b == 0:
        return a
    else:
        return ((3*a + b) * pow(3, b-1, mod))

for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        rightQ -= (1 if S[i] == "?" else 0)
        count += mult(leftA, leftQ, mod) * mult(rightC, rightQ, mod)
        count %= mod
        leftQ += (1 if S[i] == "?" else 0)
    elif S[i] == "A":
        leftA += 1 
    else:
        rightC -= 1
print(count)