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

s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7

count = 0
for i in range(len(s)):
    dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + (3**count)
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + (3**count)
    else:
        dp2['A'] = dp1['A']

    if s[i] == '?':
        dp2['AB'] = dp1['AB']*3 + dp1['A']
    elif s[i] == 'B':
        dp2['AB'] = dp1['AB'] + dp1['A']
    else:
        dp2['AB'] = dp1['AB']

    if s[i] == '?':
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    elif s[i] == 'C':
        dp2['ABC'] = dp1['ABC'] + dp1['AB']
    else:
        dp2['ABC'] = dp1['ABC']

    if s[i] == '?':
        count += 1

    for j in dp2.keys():
        dp2[j] = dp2[j] % c
    dp1 = dp2.copy()
    #print(i, dp1)

print(dp1['ABC'])


### FIXED CODE ###

s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7
n = len(s)
tmp = [1]*n
for i in range(1, n):
    tmp[i] = (tmp[i-1] * 3)%c
#print(tmp)

count = 0
for i in range(n):
    #dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    # if s[i] == '?':
    #     dp2['A'] = dp1['A']*3 + (3**count)
    # elif s[i] == 'A':
    #     dp2['A'] = dp1['A'] + (3**count)
    # else:
    #     dp2['A'] = dp1['A']
    #
    # if s[i] == '?':
    #     dp2['AB'] = dp1['AB']*3 + dp1['A']
    # elif s[i] == 'B':
    #     dp2['AB'] = dp1['AB'] + dp1['A']
    # else:
    #     dp2['AB'] = dp1['AB']
    #
    # if s[i] == '?':
    #     dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    # elif s[i] == 'C':
    #     dp2['ABC'] = dp1['ABC'] + dp1['AB']
    # else:
    #     dp2['ABC'] = dp1['ABC']
    #
    # if s[i] == '?':
    #     count += 1

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + tmp[count]
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + tmp[count]
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    # for j in dp2.keys():
    #     dp2[j] = dp2[j] % c\
    # dp1 = dp2

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    #print(i, dp1)

print(dp1['ABC'])
### BUGGY CODE ###

from itertools import product


def main():
    N, Y = (int(x) for x in input().split(" "))
    y10 = 10000
    y5 = 5000
    y1 = 1000
    max_y10 = Y // y10
    max_y5 = Y // y5
    max_y1 = Y // y1
    if (max_y10) > N:
        max_y10 = N
    if (max_y5) > N:
        max_y5 = N
    if (max_y1) > N:
        max_y1 = N
    for n_y10, n_y5, n_y1 in product(
            range(max_y10, -1, -1),
            range(max_y5, -1, -1),
            range(max_y1, -1, -1)):
        if (n_y10 + n_y5 + n_y1) != N:
            continue
        if n_y10 * y10 + n_y5 * y5 + n_y1 * y1 == Y:
            print(n_y10, n_y5, n_y1)
            exit()
    print(-1, -1, -1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from itertools import product, takewhile
# count = 0


def iter_break():
    yield True
    raise StopIteration


def main():
    N, Y = (int(x) for x in input().split(" "))
    Y = Y//1000
    y10 = 10
    y5 = 5
    y1 = 1
    max_y10 = Y // y10
    max_y5 = Y // y5
    max_y1 = Y // y1
    if (max_y10) > N:
        max_y10 = N
    if (max_y5) > N:
        max_y5 = N
    # if (max_y1) > N:
    #     max_y1 = N
    for (n_y10, n_y5) in product(
        range(max_y10, -1, -1),
            range(max_y5, -1, -1)):
        n_y1 = N-n_y10-n_y5
        if n_y1 < 0 or (n_y10 * y10 + n_y5 * y5 + n_y1 * y1 != Y):
            continue
        print(n_y10, n_y5, n_y1)
        exit()
    print(-1, -1, -1)


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

def lowerBound(nums, target):
    lp = 0
    rp = len(nums) - 1
    mp = lp + rp >> 1
    while lp <= rp:
        mp = lp + rp >> 1
        if nums[mp] == target:
            return mp
        if nums[mp] < target:
            lp = mp + 1
        else:
            rp = mp - 1
    return mp if target < nums[mp] else -1

if __name__ == '__main__':
    N = int(input())
    L = [int(l) for l in input().split()]
    L.sort()
    ret = 0
    for idx in range(len(L) - 1, 1, -1):
        for jdx in range(idx - 1, 0, -1):
            c = L[idx] - L[jdx] + 1
            ldx = lowerBound(L[:jdx], c)
            if ldx == -1: continue
            ret += jdx - ldx
    print(ret)

### FIXED CODE ###

from bisect import *
if __name__ == '__main__':
    N = int(input())
    L = sorted(map(int, input().split()))
    print(sum(jdx - bisect(L, a - L[jdx], 0, jdx) for idx, a in enumerate(L) for jdx in range(idx)))
### BUGGY CODE ###

N = int(input())
arr = list(map(int,input().split()))
def S1(a,b):
    c,last,ans = 0,0,0
    for t in range(N):
        c += 1
        if c % 2 == a:
            while last+arr[t] <= 0:
                ans += 1
                last += 1
        elif c % 2 == b:
            while last +arr[t] >= 0:
                ans +=1
                last -= 1
        last += arr[t]
    return ans
aa = S1(1,0)
bb = S1(0,1)
print(min(aa,bb))

### FIXED CODE ###

N = int(input())
arr = list(map(int,input().split()))
def S1(a,b):
    c,total,ans = 0,0,0
    for t in arr:
        c += 1
        if c % 2 == a:
            if total+t <= 0:
                ans += abs(total+t)+1
                total = 1
                continue
        elif c % 2 == b:
            if total+t >= 0:
                ans += abs(total+t)+1
                total = -1
                continue
        total += t
    return ans
print(min(S1(1,0),S1(0,1)))
### BUGGY CODE ###

import numpy as np

N = int(input())
B = [int(i)*2 for i in input().split()]

a = [[0]*N for i in range(N)]

for i in range(N-1):
    a[i][i] += 1
    a[i][i+1] += 1

a[-1][0] += 1
a[-1][-1] += 1

A = np.array(a)
b = np.array(B)

x = np.linalg.solve(A, b)

for i in x:
    print(int(i), end=" ")

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
a = [int(i) for i in input().split()]

s = sum(a)
x = [None]*N
x[0] = s - 2 * (sum(a[1::2]))

for i in range(1,N):
    x[i] = 2 * a[i-1] - x[i-1]

print(*x)
### BUGGY CODE ###

N = int(input())
S = input()

ans_list = []

for i in range(0,N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            S_ans = S[i] + S[j] +S[k]
            ans_list.append(S_ans)

set_ans = set(ans_list)
print(len(set_ans))


### FIXED CODE ###

N = int(input())
S = input()

ans = 0

for i in range(10):
    a = S.find(str(i))
    if a == -1:
        continue
    for j in range(10):
        b = S.find(str(j),a+1)
        for k in range(10):
            if b == -1:
                continue
            c = S.find(str(k),b+1)
            if c > b :
                ans +=1
print(ans)
### BUGGY CODE ###

a,b,k=map(int,input().split())
ab=[int(i) for i in range(a,b+1)]
abx=ab[:k]+ab[-k:]
if (b-a+1)>=2*k:
    for i in abx:
        print(i)
else:
    for i in ab:
        print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
l=range(a,b+1)
for i in sorted(set(l[:k])|set(l[-k:])):
    print(i)
### BUGGY CODE ###

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


def main():
    s = str(input())
    q = int(input())
    s = s.strip()
    a = [''] * (10**5*2)
    a.extend(list(s))
    a.extend([''] * (10**5*2))
    start = 10**5*2
    end = start + len(s) - 1
    for i in range(q):
        query = input().split()
        if query[0] == '1':
            a.reverse()
            tmp = end
            end = len(a)-start-1
            start = len(a)-tmp-1
        elif query[0] == '2':
            if query[1] == '1':
                a[start-1] = query[2]
                start -= 1
            elif query[1] == '2':
                a[end+1] = query[2]
                end += 1
    print(''.join(a[start:end+1]))


main()


### FIXED CODE ###

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


def main():
    s = str(input())
    q = int(input())
    s = s.strip()
    a = [''] * (10**5*2)
    a.extend(list(s))
    a.extend([''] * (10**5*2))
    start = 10**5*2
    end = start + len(s) - 1
    frip = False
    for i in range(q):
        query = input().split()
        if query[0] == '1':
            frip = not frip
        elif query[0] == '2':
            if (query[1] == '1' and frip == False) or (query[1] == '2' and frip == True):
                a[start-1] = query[2]
                start -= 1
            else:
                a[end+1] = query[2]
                end += 1
    if frip:
        a.reverse()
        tmp = end
        end = len(a)-start-1
        start = len(a)-tmp-1
    print(''.join(a[start:end+1]))


main()
### BUGGY CODE ###

def main():
    from sys import stdin
    input = stdin.readline

    n, m, s, t = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    g_yen = [[] for _ in [0]*n]
    [g_yen[u-1].append([v-1, a]) for u, v, a, b in uvab]
    [g_yen[v-1].append([u-1, a]) for u, v, a, b in uvab]

    g_snk = [[] for _ in [0]*n]
    [g_snk[u-1].append([v-1, b]) for u, v, a, b in uvab]
    [g_snk[v-1].append([u-1, b]) for u, v, a, b in uvab]

    import heapq

    inf = 10**15

    yen = [inf for _ in [0]*n]
    h = [(0, s-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if yen[i] == inf:
            yen[i] = d
            for x, y in g_yen[i]:
                heapq.heappush(h, (d+y, x))

    snk = [inf for _ in [0]*n]
    h = [(0, t-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if snk[i] == inf:
            snk[i] = d
            for x, y in g_snk[i]:
                heapq.heappush(h, (d+y, x))

    cost = [yen[i]+snk[i] for i in range(n)]
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(m, cost[i])
        cost[i] = m

    for i in cost:
        print(10**15-i)


main()


### FIXED CODE ###

n,m,s,t=map(int,input().split())
uvab=[list(map(int,input().split())) for _ in [0]*m]
g_yen=[[] for _ in [0]*n]
[g_yen[u-1].append([v-1,a]) for u,v,a,b in uvab]
[g_yen[v-1].append([u-1,a]) for u,v,a,b in uvab]

g_snk=[[] for _ in [0]*n]
[g_snk[u-1].append([v-1,b]) for u,v,a,b in uvab]
[g_snk[v-1].append([u-1,b]) for u,v,a,b in uvab]

import heapq
def dijkstra(g,start):
    inf=10**15
    dist=[inf for _ in [0]*n]
    h=[(0,start)]
    heapq.heapify(h)
    while h:
        d,i=heapq.heappop(h)
        if dist[i]==inf:
            dist[i]=d
            for x,y in g[i]:
                heapq.heappush(h,(d+y,x))
    return dist

yen=dijkstra(g_yen,s-1)
snk=dijkstra(g_snk,t-1)

cost=[yen[i]+snk[i] for i in range(n)]
m=cost[-1]
for i in range(n-1,-1,-1):
    m=min(m,cost[i])
    cost[i]=m
    
for i in cost:
    print(10**15-i)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
tmp = input().split(' ')
A = []
for i in range(N):
    A = A + [int(tmp[i])]

Z = np.array([[abs(j - i) for j in range(N)] for i in range(N)])

B = [0]*5
while K > 0:
    K = K - 1
    Ac = np.array([A]*N-Z)
    for i in range(N):
        B[i] = np.count_nonzero(Ac[i] >= 0)

    A[:] = B[:]

print(' '.join(map(str,A)))

### FIXED CODE ###

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

    Z = [N]*N

    while K > 0 and A != Z:
        K-=1
        B = [int(0)]*(N+1)
        for i in range(N):
            B[max(int(0),i-A[i])]+=1
            B[min(N-1,i+A[i])+1]-=1
        for i in range(1,N):
            B[i]+=B[i-1]

        A = B[0:N]

    print(' '.join(map(str,A)))

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

h, w = map(int, input().split())
dat = []
for i in range(h):
    dat.append(list(input()))

#print(dat)
def clear_maze(sx, sy, gx, gy, maze):
    INF = 100000000
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(40)] for j in range(40)]
    def bfs():
        queue = []
        queue.insert(0, (sx, sy))
        distance[sx][sy] = 0
        while len(queue):
            x, y = queue.pop()
            if x == gx and y == gy:
                break
            #print("seek {0} {1}".format(x, y))
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1
        return distance[gx][gy]
    return bfs()

res = -1
for yy in range(0, h):
    for xx in range(0, w):
        if dat[yy][xx] == "#":
            continue
        for yyy in range(0, h):
            for xxx in range(0, w):
                if dat[yyy][xxx] == "#":
                    continue
                step = clear_maze(yy, xx, yyy, xxx, dat)
                #print("s={0},{1} g={2},{3} cost = {4}".format(xx,yy,xxx,yyy,step))
                if step == 100000000:
                    continue
                res = max(res, step)
print(res)

### FIXED CODE ###

from pprint import pprint

INF = 1000000
dx = [1, -1, 0,  0]
dy = [0,  0, 1, -1]

# 入力
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * w + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))

# 迷路ををグラフにする。
for y in range(h):
    for x in range(w):
        if maze[y][x] == "#": # そのマスが壁なら何もしない(他のマストの連結はないので)
            continue
        # ワーシャルフロイドでは自分自身へのコストは0にしておく。
        dp[wsmap(y, x)][wsmap(y, x)] = 0
        # ４方向に移動できるかの判定
        for dir in range(len(dx)):
            nx, ny = x + dx[dir], y + dy[dir]
            if -1 < nx and nx < w and -1 < ny and ny < h: # 枠をはみ出ないかチェック
                if maze[ny][nx] != "#": # そのマスが壁でないなら
                    #print(wsmap(y, x))
                    #print("--")
                    #print("y, x {0}, {1}".format(ny, nx))
                    #print(wsmap(ny, nx))
                    dp[wsmap(y, x)][wsmap(ny, nx)] = 1 # コストを1にする

# ワーシャルフロイドする
for kk in range(h * w):
    for ii in range(h * w):
        for jj in range(h * w):
            dp[ii][jj] = min(dp[ii][jj], dp[ii][kk] + dp[kk][jj])

# これで結果が出たので
#print(dp)
res = -1
for i in range(h * w):
    for j in range(h * w):
        if dp[i][j] != INF:
            res = max(res, dp[i][j])
print(res)
### BUGGY CODE ###

import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, T = rl()
A = np.array(rl())
answer = 1
profit = 0
for i in range(N):
    p = A[i:].max() - A[i]
    if p > profit:
        profit = p
        answer = 1
    elif p == profit:
        answer += 1

print(answer)

# 40

### FIXED CODE ###

import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, T = rl()
A = rl()
answer = 1
profit = 0
min = A[0]
for i in range(1, N):
    if A[i] < min:
        min = A[i]
        continue
    x = A[i] - min
    if x > profit:
        answer = 1
        profit = x
    elif x == profit:
        answer += 1

print(answer)
# 40
### BUGGY CODE ###

def is_ok(a, b, c):
    # if a < b + c:
    #     if b < c + a:
    if c < a + b:
        return True
    return False


def main():
    n = int(input())
    l_list = list(map(int, input().split()))
    l_list.sort()

    ans = 0
    for i, a in enumerate(l_list):
        for j, b in enumerate(l_list[i+1:]):
            for k, c in enumerate(l_list[i+1+j+1:]):
                if is_ok(a, b, c):
                    ans += 1
                else:
                    break
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect


def main():
    n = int(input())
    l_list = list(map(int, input().split()))
    l_list.sort()

    ans = 0
    for i, a in enumerate(l_list):
        for j, b in enumerate(l_list[i+1:]):
            x = a + b
            temp = bisect.bisect_left(l_list, x)
            ans += temp - (i + 1 + j + 1)
    print(ans)


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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.extend([b]*e)
        b, e = b + 1, 0
    if n > 1:
        fct.extend([n]*1)
    return fct

N = int(input())
arr = factorize(N)
M = len(arr)
ans = N
for i in range(2**(M-1)):
    A = 1
    B = 1
    for j in range(M):
        if (i>>j)&1:
            A *= arr[j]
    B = N//A
    A = max(A-1,0)
    B = max(B-1,0)
    ans = min(ans,A+B)

print(ans)

### FIXED CODE ###

import math
N = int(input())
tmp = math.ceil(N**(1/2))
ans = N
for i in range(1,tmp+1):
    if N%i == 0:
        A = max(N//i-1,0)
        B = max(i-1,0)
        ans = min(ans,A+B)

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

def ABC073C_WriteAndErase():
    N = int(input().strip())
    
    Ai = []
    for i in range(N):
        num = int(input())

        if num in Ai:
            Ai.remove(num)
        else:
            Ai.append(num)

    print(len(Ai))
    

def main():
    ABC073C_WriteAndErase()

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter
def ABC073C_WriteAndErase():
    N = int(input().strip())
    Ai = [int(input().strip()) for i in range(N)]


    Bi = Counter(Ai)
    count = 0
    for key, val in Bi.items():
        if val % 2 == 1:
            count += 1

    print(count)
    

def main():
    ABC073C_WriteAndErase()

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

import sys
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

N = int(input())

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

dp = [-1] * (1 << N)
dp[(1 << N) - 1] = 1

def dfs(group, count):
    if dp[group] != -1:
        return dp[group]
    res = 0
    for i in range(N):
        if (group >> i) & 1 == 0 and A[count][i] == 1:
            res += dfs(group + (1 << i), count + 1)
    dp[group] = res % MOD
    return dp[group]

tmp = dfs(0, 0)

print (tmp)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

N = int(input())

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

dp = [-1] * (1 << N)
dp[(1 << N) - 1] = 1

def dfs(group, count):
    if dp[group] != -1:
        return dp[group]
    res = 0
    for i in range(N):
        if (group >> i) & 1 == 0 and A[count][i] == 1:
            res += dfs(group + (1 << i), count + 1)
    dp[group] = res % MOD
    return dp[group]

tmp = dfs(0, 0)

print (tmp)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    d={}
    c=0
    edge1=[[] for _ in range(N*(N-1)//2)]
    edge2=[[] for _ in range(N*(N-1)//2)]
    for i in range(N):
        l=list(map(lambda x: int(x)-1,input().split()))
        prev=-1
        for x in l:
            if min(i,x)*10**3+max(i,x) in d:
                if prev!=-1:
                    edge1[prev].append(d[min(i,x)*10**3+max(i,x)])
                    edge2[d[min(i,x)*10**3+max(i,x)]].append(prev)
            else:
                d[min(i,x)*10**3+max(i,x)]=c
                if prev!=-1:
                    edge1[prev].append(c)
                    edge2[c].append(prev)
                c+=1
            prev=d[min(i,x)*10**3+max(i,x)]
    stack=[]
    days=[-1]*(N*(N-1)//2)
    for i,l in enumerate(edge2):
        if not l:
            stack.append(i)
            days[i]=1
    if stack:
        for _ in range(5*10**7):
            v=stack.pop()
            for x in edge1[v]:
                if days[x]<days[v]+1:
                    days[x]=days[v]+1
                    stack.append(x)
            if not stack:
                print(max(days))
                exit()
    print(-1)
        

    

        
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=[[] for _ in range(N)]
    for i in range(N):
        A[i]=deque(list(map(lambda x: int(x)-1,input().split())))
    days=1
    c=0
    pre=[]
    tmp=[]
    for i in range(N):
        if A[i] and A[A[i][0]][0]==i:
            tmp.append(i)
            tmp.append(A[i][0])
    tmp=list(set(tmp))
    for i in tmp:
        A[i].popleft()
        c+=1
    pre=tmp
    if c<N*(N-1):
        while c<N*(N-1):
            tmp=[]
            for i in pre:
                if A[i] and A[A[i][0]][0]==i:
                    tmp.append(i)
                    tmp.append(A[i][0])
            tmp=list(set(tmp))
            for i in tmp:
                A[i].popleft()
                c+=1
            pre=tmp
            days+=1
            if days>N*(N-1)//2:
                print(-1)
                exit()
    print(days)
                
            
        
    
        
        

    

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

import math

k = int(input())

total = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):

            if a == b == c:
                total += a
                continue

            if a == 1:
                total += a
                continue

            if b == 1:
                total += b
                continue

            if c == 1:
                total += c
                continue

            if a % b == 0:
                total += math.gcd(b,c)
                continue
            
            if b % a == 0:
                total += math.gcd(a,c)
                continue

            total += math.gcd(math.gcd(a,b),c)

print(total)

### FIXED CODE ###

import math

k = int(input())
k_arr = range(1,k+1)

a_arr = list()
b_arr = list()

for k in k_arr:
    for a in k_arr:
        a_arr.append(a)

for b in k_arr:
    for k in k_arr:
        b_arr.append(b)

gcds = list(map(math.gcd,a_arr,b_arr))

total = 0
for c in k_arr:
    c_arr = [c] * k * k
    total += sum(map(math.gcd,gcds,c_arr))

print(total)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
bit = [0]*60
ans = 0
mod = 10**9+7
for i in a:
    cnt = 1
    while i:
        bit[-cnt] += i%2
        i //= 2
        cnt += 1
for i in range(60):
    ans += (n-bit[-1-i])*bit[-1-i] * (2**i) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
bit = [0]*60
ans = 0
mod = 10**9+7
for i in a:
    cnt = 1
    while i:
        bit[-cnt] += i%2
        i //= 2
        cnt += 1
for i in range(60):
    ans += (n-bit[-1-i])*bit[-1-i] * (2**i) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n, m = [int(i) for i in input().split()]
fibo_l = [1, 1] + [None] * (n - 1)
a = [int(input()) for i in range(m)]

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x - 1) + fibo(x - 2)
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n, m = [int(i) for i in input().split()]
fibo_l = [1] + [None] * n
a = set([int(input()) for i in range(m)])

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x-1) % 1000000007 + fibo(x-2) % 1000000007
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)