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

#import numpy as np

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

for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

#print(A)

S = [0 for i in range(n)]

n1n = n*(n-1)

d = 0
for ii in range(n*n*2):
    co = 0
    i = 0
    F = [0 for i in range(n)]
    ga = 0
    while co < n:
        if F[i] == 0 and S[i] <= n-2:
            aite = A[i][S[i]]
            #print(S)
            #print("aite",aite)
            if aite < n and A[aite][S[aite]] == i and F[aite] == 0:
                #print("g", i, aite)
                S[i] += 1
                S[aite] += 1
                F[i] = 1
                F[aite] = 1
                co = 0
                ga += 1
        i = (i+1) % n
        co += 1
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == n1n:
            print(d-1)
        else:
            print(-1)
        break



### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

AA = [[j for j in i] for i in A]

ID = [[-1] * n for i in range(n)]
id_ = 0
for i in range(n):
    for j in range(i+1,n):
        ID[i][j] = id_
        ID[j][i] = id_
        id_ += 1

for i in range(n):
    for j in range(n-1):
        A[i][j] = ID[i][A[i][j]]

M = [[] for i in range(id_)]
IN = [0] * id_
for i in range(n):
    for j in range(n-2):
        M[A[i][j]].append(A[i][j+1])
        IN[A[i][j+1]] +=1
# print(A)
# print(M)

# 以下、トポロジカルソート

S = []
s = 0

for i in range(id_):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        # print(x,IN)
        if IN[x] == 0:
            S.append(x)
    s += 1

# print(S)

if len(S) < id_:
    print(-1)
else:
    T = [1] * id_
    for i in range(id_):
        for j in M[S[i]]:
            T[j] = max(T[j], T[S[i]] + 1)
    print(max(T))


# 以下、閉路検出(今は削除)

# V = [0] * id_
# S = [0]
# V[0] = 1

# import sys

# def visit(x):
#     if V[x] == 1:
#         print(-1)
#         sys.exit()
#     elif V[x] == 0:
#         V[x] = 1
#         for i in M[x]:
#             visit(i)
#         V[x] = 2

# for i in range(id_):
#     if V[i] == 0:
#         visit(i)
# print("heironasi")

# 閉路検出ここまで
### BUGGY CODE ###

import numpy as np 
#input
N = int(input())
A = np.array(list(map(int, input().split())))

#output
idx = np.argsort(-A)

dp = np.zeros((N+1, N+1), int)
#dp[i, j]を左i, 右jまで場所が決まった状態の最大値とする。
#i+j = Nとなる場合の最大値が答えとなる。
for i in range(N):
    dp[i+1, 0] = dp[i, 0] + A[idx[i]]*(abs(idx[i]-i))
for j in range(N):
    dp[0, j+1] = dp[0, j] + A[idx[j]]*(abs(N-1-idx[j]-j))

for i in range(N):
    for j in range(N):
        if i+j+1 < N:
            dp[i+1, j+1] = max(dp[i, j+1]+A[idx[i+j+1]]*(abs(idx[i+j+1]-i)), dp[i+1, j] + A[idx[i+j+1]]*(abs(N-1-idx[i+j+1]-j)))

answer = 0        
for i in range(N):
    answer = max(answer, dp[i, N-i])

print(answer)

### FIXED CODE ###

#python3ではTLE
#input
N = int(input())
A = list(map(int, input().split()))

#output
B = [(i, a) for i, a in enumerate(A)]
B = sorted(B, key = lambda x:x[1], reverse = True)

dp = [[0] * (N+1) for i in range(N+1)]
#dp[i, j]を左i, 右jまで場所が決まった状態の最大値とする。
#i+j = Nとなる場合の最大値が答えとなる。

answer = 0
for i in range(N):
    dp[i+1][0] = dp[i][0] + B[i][1]*(abs(B[i][0]-i))
    for j in range(N):
        dp[0][j+1] = dp[0][j] + B[j][1]*(abs(N-1-B[j][0]-j))
        if i+j+1 < N:
            dp[i+1][j+1] = max(dp[i][j+1]+B[i+j+1][1]*(abs(B[i+j+1][0]-i)), dp[i+1][j] + B[i+j+1][1]*(abs(N-1-B[i+j+1][0]-j)))
    answer = max(answer, dp[i][N-i])

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

def main():
    MOD = 10 ** 9 + 7

    s = input()
    n = len(s)

    acc_a = [0] * (n + 1)
    acc_c = [0] * (n + 1)
    acc_q = [0] * (n + 1)

    a = 0
    c = 0
    q = 0
    for i, char in enumerate(s, 1):
        if char == 'A':
            a += 1
        elif char == 'C':
            c += 1
        elif char == '?':
            q += 1
        acc_a[i] = a
        acc_c[i] = c
        acc_q[i] = q

    ans = 0
    for i, char in enumerate(s, 1):
        if char == 'B' or char == '?':
            t = 0
            t += acc_a[i - 1] * (acc_c[n] - acc_c[i]) * pow(3, acc_q[n] - int(char == '?'))
            t += acc_a[i - 1] * (acc_q[n] - acc_q[i]) * pow(3, acc_q[n] - 1 - int(char == '?'))
            t += acc_q[i - 1] * (acc_c[n] - acc_c[i]) * pow(3, acc_q[n] - 1 - int(char == '?'))
            t += acc_q[i - 1] * (acc_q[n] - acc_q[i]) * pow(3, acc_q[n] - 2 - int(char == '?'))
            t %= MOD
            ans = (ans + t) % MOD
    print(int(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

s = input()
ls = len(s)
dp = [[0 for _ in range(4)] for _ in range(ls+1)]
dp[0][0] = 1
mod = 10 ** 9 + 7

for i in range(1, ls+1):
    for j in range(4):
        #'?'のとき'ABC'の3通りに分岐させ、いずれも取らないので3倍
        dp[i][j] += dp[i-1][j] * (3 if s[i-1] == '?' else 1)
        if j > 0:
            #ほしい文字に変えた場合　または　ほしい文字の場合で取ったとき
            dp[i][j] += dp[i-1][j-1] if s[i-1] == 'ABC'[j-1] or s[i-1] == '?' else 0
        dp[i][j] %= mod
print(dp[ls][3])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)

sys.setrecursionlimit(100000)

N, X = map(int, input().split())

def f(x, n):
    debug(x,n)
    # if 2*x == n:
    #     return 3*x
    if x % (n-x) == 0:
        return 3*x
    if 2*x < n:
        return f(x, n-x) + 3*x# n + x
    a = x//(n-x) + 1
    t = a*(n-x) - x
    return f(n-x-t, n-x) + 3*x # + t

print(f(X, N))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)

sys.setrecursionlimit(100000)

N, X = map(int, input().split())

def f(x, n):
    if x == 0 or x == n:
        return 0
    debug(x,n)
    # if 2*x == n:
    #     return 3*x
    if x % (n-x) == 0:
        return 3*x
    if 2*x < n:
        # return f(x, n-x) + 3*x# n + x
        return f(n-x, n)
    a = x//(n-x) + 1
    t = a*(n-x) - x
    return f(n-x-t, n-x) + 3*x # + t

print(f(X, N))
### BUGGY CODE ###

K,S=map(int,input().split())
x=y=z=0
cnt=0
for l in range(K+1):
  for m in range(K+1):
    for n in range(K+1):
      if l+m+n==S:
        cnt+=1
print(cnt)

### FIXED CODE ###

K,S=map(int,input().split())
cnt=0
for x in range(K+1):
  for y in range(K+1):
    z=S-x-y
    if 0<=z and z<=K:
      cnt+=1
print(cnt)
### BUGGY CODE ###

cache = {}

def memoize(f):
  global cache
  def _(*args):
    if not args in cache:
      cache[args] = f(*args)
    return cache[args]
  return _

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]

@memoize
def f(i, w, v):
  if i == n:
    return v
  if d[i][0] <= w:
    return max(f(i + 1, w - d[i][0], v + d[i][1]), f(i + 1, w, v))
  else:
    return f(i + 1, w, v)  
print(f(0, w, 0))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

def f(n,m):
     a = list(map(int,input().split()))
     min_a = min(a)
     a = [(1,i) for i in a]
     b_c = [tuple(map(int,input().split())) for i in range(m)]
     a += b_c
     a.sort(reverse=True,key=lambda x:x[1])
     ans = 0
     while True:
          if n>a[0][0]:
               ans += a[0][0]*a[0][1]
               n -= a[0][0]
               a.pop(0)
          else:
               ans += a[0][1]*n
               break
     print(ans)

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

### FIXED CODE ###

def f(n,m):
     a = list(map(int,input().split()))
     min_a = min(a)
     a = [(1,i) for i in a]
     b_c = [tuple(map(int,input().split())) for i in range(m)]
     a += b_c
     a.sort(key=lambda x:x[1])
     ans = 0
     while True:
          if n>a[-1][0]:
               ans += a[-1][0]*a[-1][1]
               n -= a[-1][0]
               a.pop()
          else:
               ans += a[-1][1]*n
               break
     print(ans)

n,m = map(int,input().split())
f(n,m)
### BUGGY CODE ###

from math import sqrt
from fractions import gcd
from collections import defaultdict
from copy import deepcopy

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

def f(n):
    d = defaultdict(int)
    if n % 2 == 0:
        r = 0
        while n % 2 == 0:
            n //= 2
            r += 1
        d[2] = r
    for i in range(3,int(sqrt(n))+1,2):
        if n % i == 0:
            s = 0
            while n % i == 0:
                n //= i
                s += 1
            d[i] = s
    if n != 1:
        d[n] = 1
    return d

B = [f(A[i]) for i in range(N)]

lp = deepcopy(B[0])

for i in range(N-1):
    for j in list(B[i+1].keys()) + list(lp.keys()):
        lp[j] = max(B[i+1][j],lp[j])

ans = 0

for i in range(N):
    r = 1
    for j in list(lp.keys()):
        r = (r*pow(j,lp[j]-B[i][j],mod)) % mod
    ans = (ans + r) % mod

print(ans)

### FIXED CODE ###

def main():
    from math import sqrt
    from fractions import gcd
    from collections import defaultdict
    from copy import deepcopy

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

    p = [1] * (1001)
    P = []  # 1000までの素数表
    p[0] = p[1] = 0
    for x in range(2, int(sqrt(1000000)) + 1):
        if p[x]:
            P.append(x)
            for y in range(x * x, 1001, x):
                p[y] = 0

    B = [defaultdict(int) for i in range(N)]  # N個の数を素因数分解したもの
    lcm = defaultdict(int)  # N個の数のlcmを素因数分解したもの

    for i in range(N):
        for j in P:
            if A[i] % j == 0:
                while A[i] % j == 0:
                    A[i] //= j
                    B[i][j] += 1
            lcm[j] = max(lcm[j], B[i][j])
        if A[i] != 1:
            B[i][A[i]] = 1
            lcm[A[i]] = 1

    l = 1  # N個の数のlcm
    for i in lcm.keys():
        l = (l * pow(i, lcm[i], mod)) % mod

    ans = 0
    # l/A[i]の和を求めていく
    for i in range(N):
        r = l
        for j in list(B[i].keys()):
            r = (r * pow(j, mod - B[i][j] - 1, mod)) % mod
        ans = (ans + r) % mod

    print(ans)

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

n, p = [int(i) for i in input().split()]
max_x = int(p**(1/n))
ans = 1
if n >= p:
    print(1)
else:
    for i in range(max_x+1, 1, -1):
        if p % i**n == 0:
            ans = i
            break
    print(ans)

### FIXED CODE ###

n, p = [int(i) for i in input().split()]
tmp = p**(1/n)
if tmp - int(tmp) > 0.999:
    max_x = int(tmp) + 1
else:
    max_x = int(tmp)
ans = 1
for i in range(max_x, 1, -1):
    if p % pow(i,n) == 0:
        ans = i
        break
print(ans)
### BUGGY CODE ###

import itertools
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        L = list(map(int, input().split()))

        ans = 0

        for a,b,c in itertools.combinations(L,3):
            if a < b + c and b < c + a and c < a + b:
                ans += 1

        print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()


### FIXED CODE ###

import bisect
import itertools
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        L = list(map(int, input().split()))

        ans = 0
        L.sort()

        for i in range(N - 2):
            for j in range(i + 1, N - 1):
                ind = bisect.bisect_left(L, L[i] + L[j])
                ans += ind - j - 1

        print(ans)


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

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

maxh = [i for i, x in enumerate(h) if x==max(h)]
minh = [i for i, x in enumerate(h) if x==min(h)]

if min(maxh)<max(minh) and max(h)-1>min(h):
    print("No")
else:
    print("Yes")

### FIXED CODE ###

n = int(input())
h=list(map(int,input().split()))
def jud(n,h):
    for i in list(reversed(range(0,n-1))):
        # print(h[i],h[i+1])
        if h[i+1]-h[i]==-1:
            h[i]-=1
            # print(h[i])
            continue
        if h[i]-h[i+1]>1:
            return "No"
            break
    return "Yes"

print(jud(n,h))
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]
dp = [10**10] * N
dp[0] = 0
for i in range(1, N):
    for j in range(1, K+1):
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i-j]))
print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]
dp = [10**10] * N
dp[0] = 0
for i in range(1, N):
    for j in range(1, K+1):
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i-j]))
print(dp[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [int(x) for x in input().split()]
a.sort()

ans = [-1, 0, 0]

from math import factorial

def comb(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))

import bisect

for i in a[1:]:
    idx = [bisect.bisect_left(a, i // 2), bisect.bisect_left(a, i // 2) - 1]
    for j in idx:
        if i == a[j]:
            continue
        else:
            if i < a[j]:
                continue
            elif comb(i, a[j]) > ans[0]:
                ans = [comb(i, a[j]), i, a[j]]

print(*ans[1:])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [int(x) for x in input().split()]
a.sort()

ans = [-1, 0, 0]

import bisect

i = a[-1]
idx = [bisect.bisect_left(a, i / 2), bisect.bisect_left(a, i / 2) - 1]

if abs(i / 2 - a[idx[0]]) < abs(i // 2 - a[idx[1]]):
    print(i, a[idx[0]])    
else:
    print(i, a[idx[1]])
### BUGGY CODE ###

import sys
from collections import defaultdict

n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353

d2 = [1]
tmp = 1
for i in range(n):
    tmp = tmp * 2 % MOD
    d2.append(tmp)

s = sum(aaa)
dp = [defaultdict(lambda: 0) for _ in [0] * (s + 1)]
dp[0][0] = 1
tmp_sum = 0
for a in aaa:
    for i in range(tmp_sum, -1, -1):
        dd = dp[i]
        if not dd:
            continue
        for k, p in dd.items():
            dp[i + a][k + 1] += p
    tmp_sum += a

ans = pow(3, n, MOD)
sub = 0
h = (s + 1) // 2
for dd in dp[h:]:
    for k, p in dd.items():
        sub += d2[n - k] * p * 3
    sub %= MOD
if s % 2 == 0:
    dd = dp[h]
    for k, p in dd.items():
        sub -= p * 3

ans = (ans - sub) % MOD
print(ans)


### FIXED CODE ###

import sys

n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353

s = sum(aaa)
dp1 = [0] * (s + 1)
dp2 = [0] * (s + 1)
dp1[0] = 1
dp2[0] = 1
tmp_sum = 0
for a in aaa:
    for i in range(tmp_sum, -1, -1):
        dp1[i + a] += dp1[i]
        dp1[i] *= 2
        dp2[i + a] += dp2[i]
    for i in range(tmp_sum, -1, -1):
        dp1[i] %= MOD
        dp2[i] %= MOD
    tmp_sum += a

h = (s + 1) // 2
ans = (pow(3, n, MOD) - sum(dp1[h:]) * 3) % MOD
if s % 2 == 0:
    ans = (ans + dp2[h] * 3) % MOD
print(ans)
### BUGGY CODE ###

from collections import Counter
s = input()
s = s[::-1]
# 累積和の準備
sum_list = [0]*(len(s)+1)  # s[0]は０であってほしいから配列数ひとつおおい
for i in range(1, len(s) + 1):
    sum_list[i] += sum_list[i-1] + int(s[i-1])*10**(i-1)
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
# s[i]のmod=2019を記憶しておくリスト用意
mod_s = [[] for _ in range(len(sum_list))]
mod_s[0] = 0
for i in range(1, len(sum_list)):
    mod_s[i] = sum_list[i] % 2019

#print(mod_s)
c = Counter(mod_s)
ans = 0
#print(c)
for value in c.values():
    if value > 1:
        ans += value*(value-1)//2
print(ans)






### FIXED CODE ###

from collections import Counter
s = input()
n = len(s)
# 累積和の準備
sum_list = [0]*(n+1)  # s[0]は０であってほしいから配列数ひとつおおい
_10 = 1
for i in range(1, n + 1):
    sum_list[i] += (sum_list[i-1] + int(s[n-i])*_10 % 2019) % 2019  # ここでmodしておく
    _10 = _10*10 %2019
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
c = Counter(sum_list)
ans = 0

for key in c.keys():
    ans += c[key]*(c[key]-1)//2
print(ans)
### BUGGY CODE ###

H,W,M=map(int,input().split())
h=[0]*M
w=[0]*M
for i in range(M):
    h[i],w[i]=map(int,input().split())
t=[0]*H
y=[0]*W
for i in range(H):
    a = 0
    for j in range(M):
        if h[j] == i+1:
            a = a+1
        t[i] = a
for i in range(W):
    a = 0
    for j in range(M):
        if w[j] == i+1:
            a = a+1
        y[i] = a       
maxt = max(t)
maxy = max(y)
lt=[]
ly=[]
for i in range(len(t)):
    if t[i] == maxt:
        lt.append(i+1)
for i in range(len(y)):
    if y[i] == maxy:
        ly.append(i+1)
b = 0
for i in range(M):
    if h[i] in lt and w[i] in ly:
        b = b + 1
if b == len(lt)*len(ly):
    print(maxt+maxy-1)
else:
    print(maxt+maxy)

### FIXED CODE ###

H,W,M=map(int,input().split())
bomb=[]
h=[0]*H
w=[0]*W
for i in range(M):
    hi,wi=map(int,input().split())
    h[hi-1] += 1
    w[wi-1] += 1
    bomb.append([hi,wi])    
maxh = max(h)
maxw = max(w)
ans = maxh +  maxw
lh=[]
lw=[]
for i in range(len(h)):
    if h[i] == maxh:
        lh.append(i+1)
for i in range(len(w)):
    if w[i] == maxw:
        lw.append(i+1)
a = 0
for i in range(M):
    if ans == h[bomb[i][0]-1]+w[bomb[i][1]-1]:
        a += 1
if a == len(lh)*len(lw):
    print(ans-1)
else:
    print(ans)
### BUGGY CODE ###

# coding: utf-8

list = input().split()
N = int(list[0])
M = int(list[1])
a = input().split()
hako = []
for i in a:
    hako.append(int(i))

ans = 0
for i in range(N):
    for j in range(N - i):
        if sum(hako[i:i+j+1]) % M == 0:
            ans += 1
print(ans)

### FIXED CODE ###

# coding: utf-8
import collections
import math
list = input().split()
N = int(list[0])
M = int(list[1])
a = input().split()
x = 0
hako = [0]
for i in a:
    hako.append(int(i))
B = []
b = 0
for i in hako:
    b += i
    B.append(b%M)
c = collections.Counter(B)
aaa =[]
for i in c:
    if c[i] >= 2:
        aaa.append(c[i])
def kumi(n):
    return int(math.factorial(n)/(2*math.factorial(n-2)))
for i in aaa:
    x += kumi(i)
print(x)
### BUGGY CODE ###

# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
    res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))


### FIXED CODE ###

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 3}
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Z = [0]*(N+1)
    if C[b+1]:
        if t1 <= b < s0:
            for (r, g), v in X.items():
                if t2 <= g < s1:
                    # r <- b+1
                    Z[g] += v
                if t2 <= r < s1:
                    # g <- b+1
                    Z[r] += v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [0]*(N+1)
        for (r, g), v in X.items():
            # r <- b+1
            Z[g] += v
            # g <- b+1
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)
### BUGGY CODE ###

N=int(input())
*A,=map(int,input().split())
t=10**9+7

ans=0
for i in range(N):
       ans+=A[i]*sum(A[i+1:])%t
print(ans%t)    

### FIXED CODE ###

N=int(input())
*A,=map(int,input().split())
t=10**9+7
S=[a%t for a in A]
g=sum(S)

ans=0
for i in range(N):
       g-=S[i]
       ans+=S[i]*g%t
print(ans%t)
### BUGGY CODE ###

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

l = [list(map(int,input().split())) for i in range(m)]


count = 0
while True:
    check = [0]* n

    for i in l:
        a,b = i

        for j in range(a,b):
            check[j] += 1
            


    index = check.index(max(check))
    count += 1
    dellist = []
    for i in range(len(l)):
        a,b = l[i][0],l[i][1]
        if index in range(a,b):
            dellist.append(i)
    num = 0
    for i in dellist:
        del l[i-num]
        num += 1

    if l == []:
        break

print(count)
            






### FIXED CODE ###

from operator import itemgetter

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

l = sorted([list(map(int,input().split())) for i in range(m)],key=itemgetter(1))



check = -1
count = 0
for a,b in l:
  if a > check:
    count += 1
    check = b-1

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

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

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = [i for i in range(10 ** 5 + 2)]
m = [0] * (10 ** 5 + 2)
for i in a:
  m[i] += 1
s = sum(a)
q = int(input())
for i in range(q):
  b, c = map(int, input().split())
  if m[b] != 0:
    s += (c - b) * m[b]
    m[c] += m[b]
    m[b] = 0
  print(s)