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

#TLEする
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n

# O(N)
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second
# print (left, right)

# O(N)
left_lst = [1] * (left + 1) 
for i in range(1, left + 1):
    left_lst[i] = (left_lst[i - 1] * (left + 1 - i)) // i
# print (left_lst)

# O(N)
right_lst = [1] * (right + 1)
for i in range(1, right + 1):
    right_lst[i] = (right_lst[i - 1] * (right + 1 - i)) // i
# print (right_lst)

def calc(i): #1を含めてトータルi個選ぶ
    count = 0
    #左側からl個、右側からr個選ぶ
    start = max((i - 1) - right, 0) #左側から最低限選ばないといけない個数
    for l in range(start, min(i, left + 1)):
        count += left_lst[l] * right_lst[i - 1 - l]
        count %= MOD
    return count

N = n + 1
tmp = 1
for i in range(1, n + 2):
    tmp = (tmp * (N + 1 - i))//i
    if left + right < i - 1:
        print (tmp % MOD)
        continue
    print ((tmp - calc(i)) % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n

# O(N)
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second

U = 10 ** 5 + 1
def power_mod(a, n):
    if n == 0:
        return 1
    x = power_mod(a//2)

def make_fact(fact, fact_inv):
    for i in range(1, U + 1):
        fact[i] = (fact[i - 1] * i) % MOD
    fact_inv[U] = pow(fact[U], MOD - 2, MOD)
    for i in range(U, 0, -1):
        fact_inv[i - 1] = (fact_inv[i] * i) % MOD

def comb(n, k):
    if k < 0 or n < k:
        return 0
    x = fact[n]
    x *= fact_inv[k]
    x %= MOD
    x *= fact_inv[n - k]
    x %= MOD
    return x

fact = [1] * (U + 1)
fact_inv = [1] * (U + 1)
make_fact(fact, fact_inv)

for i in range(1, n + 2):
    ans = comb(n + 1, i) - comb(left + right, i - 1)
    print (ans % MOD)
### BUGGY CODE ###

#import numpy as np
#import random
#import time
from collections import defaultdict, Counter

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def main():
    #N = 20
    #A = [random.randint(1, int(1e6)) for _ in range(int(N))]
    N = int(input())
    A = [int(c) for c in input().split(' ')]
    #t1 = time.time()
    dup_cnt = Counter(A)
    dup = set(x for x in dup_cnt if dup_cnt[x] > 1)
    A_set = set(A)
    if 1 in A_set:
        if 1 in dup:
            print('0')
        else:
            print('1')
        exit()
    A = list(A_set)
    N = len(A)
    A.sort()
#    B = [factorization(x) for x in A]
#    B.sort()

    d = defaultdict(list)
    B = []
    for x in A:
        x_fac = factorization(x)
        B.append(x_fac)
        for y in x_fac:
            d[y[0]].append(x)
    assert len(A)==len(B)
    #print(A)
    #print(B)
    #print(d)
    not_divided = set()
    for i in range(N):
        bi = A[i]
        bi_fac = B[i]
        can_divide = False
        for y in bi_fac:
            for a in d[y[0]]:
                if bi % a == 0 and bi != a:
                    #print(a,bi)
                    can_divide = True
                    break
                elif a > bi:
                    break
            if can_divide:
                break
        if can_divide or bi in dup:
            continue
        else:
            not_divided.add(bi)
    #print(A)
    #print(dup)
    #print(not_divided)
    print(len(not_divided))
    #print(time.time() - t1)


if __name__ == "__main__":
    main()

### FIXED CODE ###

#import random
#import time
from collections import defaultdict, Counter

def main():
    #N = 20
    #A = [random.randint(1, int(1e6)) for _ in range(int(N))]
    N = int(input())
    A = [int(c) for c in input().split(' ')]
    #t1 = time.time()
    dup_cnt = Counter(A)
    dup = set(x for x in dup_cnt if dup_cnt[x] > 1)
    A_set = set(A)
    A = list(A_set)
    A.sort()
    N = len(A)
    max_A = A[-1]
    prime = [True]*(max_A+1)
    ans = 0
    for x in A:
        if not prime[x]:
            continue
        else:
            for y in range(2*x, max_A+1, x):
                prime[y] = False
            if not x in dup:
                ans += 1
    print(ans)


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

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

if __name__ == "__main__":
    solve()

### FIXED CODE ###

def solve():
    from collections import deque
    S = input()
    s = deque(S)
    Q = int(input())
    reverse = False
    for i in range(Q):
        T = input().split()
        if T[0] == '1':
            if reverse:
                reverse = False
            else:
                reverse = True
        else:
            if T[1] == '1' and not reverse:
                s.appendleft(T[2])
            elif T[1] == '1' and reverse:
                s.append(T[2])
            elif T[1] == '2' and not reverse:
                s.append(T[2])
            else:
                s.appendleft(T[2])
    if reverse:
        print(''.join(s)[::-1])
    else:
        print(''.join(s))

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

limit, result = map(int, input().split())  

sum = 0

for x in range(limit+1):
    for y in range(limit+1):
        for z in range(limit+1):
            if x + y + z == result:
                sum = sum+1
            
            
       
        
        
            
print(sum)

### FIXED CODE ###

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

def main():
    from collections import deque

    dd = 0, 1, 0, -1

    H, W = map(int, input().split())
    G = [input() for _ in range(H)]

    def dist(sr, sc, gr, gc):
        if G[sr][sc] == '#' or G[gr][gc] == '#':
            return -1

        memo = [[-1] * W for _ in range(H)]

        dq = deque()
        dq.append((sr, sc, 0))
        while dq:
            r, c, d = dq.popleft()
            if r == gr and c == gc:
                return d

            nd = d + 1
            for i in range(4):
                nr = r + dd[i]
                nc = c + dd[i ^ 1]
                if not (0 <= nr < H and 0 <= nc < W):
                    continue
                if ~memo[nr][nc]:
                    continue
                if G[nr][nc] == '#':
                    continue
                dq.append((nr, nc, nd))
                memo[nr][nc] = nd

        return -1

    ans = 0
    for sr in range(H):
        for sc in range(W):
            for gr in range(H):
                for gc in range(W):
                    ans = max(ans, dist(sr, sc, gr, gc))

    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


### FIXED CODE ###

def main():
    from collections import deque

    h, w = map(int, input().split())

    s = [input() for _ in range(h)]

    drdc = (1, 0), (-1, 0), (0, 1), (0, -1)

    ret = -1
    for r in range(h):
        for c in range(w):
            if s[r][c] == '.':
                dist = [[-1] * w for _ in range(h)]
                dist[r][c] = 0

                q = deque()
                q.append((r, c, 0))

                md = -1
                while q:
                    qr, qc, d = q.popleft()
                    for dr, dc in drdc:
                        nr = qr + dr
                        if nr < 0 or h <= nr:
                            continue
                        nc = qc + dc
                        if nc < 0 or w <= nc:
                            continue
                        if s[nr][nc] == '#':
                            continue
                        if dist[nr][nc] != -1:
                            continue
                        nd = d + 1
                        dist[nr][nc] = nd
                        if md < nd:
                            md = nd

                        q.append((nr, nc, nd))

                ret = max(ret, md)

    print(ret)


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

N=int(input())
A=list(map(int, input().split()))
L=[0]*(100001)
#何回その数字が出てきたかのリスト
ans=0
for a in A:
  L[a]+=1
  #aが出てきた数（2回出てきたら2になる）
  ans=sum(A)
Q=int(input())
for i in range(Q):
  B,C=map(int, input().split())
  #Bの数だけ（C-B)足す、BはCに置き換わるのでLB＝０になおす。
  key=L[B]
  L[C]+=key
  ans+=key*(C-B)
  L[B]=0
  print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
L=[0]*(100001)
#何回その数字が出てきたかのリスト
ans=0
for a in A:
  L[a]+=1
  #aが出てきた数（2回出てきたら2になる）
  ans+=a
Q=int(input())
for i in range(Q):
  B,C=map(int, input().split())
  key=L[B]
  L[C]+=key
  ans+=key*(C-B)
  L[B]=0
  print(ans)
### BUGGY CODE ###

n = int(input())
a = [i for i in map(int, input().split())]

for j in range(1,n+1):
  print(a.count(j))

### FIXED CODE ###

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

for j in range(n):
    print(ans[j])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0 for i in range(n+1)]
a.reverse()
a.insert(0,0)
counter = 0
for i in range(1,n+1): #a[i]を見ている
    temp = 0
    for k in range(n+1-i,n+1): #b[k]を見ている
        if k % (n+1-i) == 0:
            temp += b[k]
    if temp%2 != a[i]:
        b[n+1-i] = 1
        counter += 1
print(counter)
for i in range(1,n+1):
    if b[i] == 1:
        if counter != 1:
            print(i,end= " ")
        else:
            print(i)
        counter -= 1


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0 for i in range(n+1)]
a.reverse()
a.insert(0,0)
counter = 0
for i in range(1,n+1): #a[i]を見ている
    temp = 0
    t = 1
    while (n+1-i)*t <= n:
        temp += b[(n+1-i)*t]
        t += 1
    if temp%2 != a[i]:
        b[n+1-i] = 1
        counter += 1
print(counter)
for i in range(1,n+1):
    if b[i] == 1:
        if counter != 1:
            print(i,end= " ")
        else:
            print(i)
        counter -= 1
### BUGGY CODE ###

mod = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]

S = sum(A)

dp1 = [[0] * (S+1) for _ in range(N+1)]
dp1[0][0] = 1
for i in range(N):
    for r in range(S+1):
        if r + A[i] < S+1:
            dp1[i+1][r+A[i]] += dp1[i][r]
            dp1[i+1][r+A[i]] %= mod
        dp1[i+1][r] += 2 * dp1[i][r]
        dp1[i+1][r] %= mod

dp2 = [[0] * (S+1) for _ in range(N+1)]
dp2[0][0] = 1
for i in range(N):
    for r in range(S+1):
        if r + A[i] < S+1:
            dp2[i+1][r+A[i]] += dp2[i][r]
            dp2[i+1][r+A[i]] %= mod
        dp2[i+1][r] += dp2[i][r]
        dp2[i+1][r] %= mod

res1 = sum(dp1[N][r] for r in range(-(-S//2), S+1))
res2 = dp2[N][S//2] if S % 2 == 0 else 0

ans = pow(3, N, mod) - (3*res1 - 3*res2)
ans %= mod
print(ans)

### FIXED CODE ###

mod = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]

S = sum(A)

dp1 = [[0] * (S+1) for _ in range(N+1)]
dp1[0][0] = 1
for i in range(N):
    for r in range(S+1):
        if r + A[i] < S+1:
            dp1[i+1][r+A[i]] += dp1[i][r]
            dp1[i+1][r+A[i]] %= mod
        dp1[i+1][r] += 2 * dp1[i][r]
        dp1[i+1][r] %= mod

dp2 = [[0] * (S+1) for _ in range(N+1)]
dp2[0][0] = 1
for i in range(N):
    for r in range(S+1):
        if r + A[i] < S+1:
            dp2[i+1][r+A[i]] += dp2[i][r]
            dp2[i+1][r+A[i]] %= mod
        dp2[i+1][r] += dp2[i][r]
        dp2[i+1][r] %= mod

res1 = sum(dp1[N][r] for r in range(-(-S//2), S+1))
res2 = dp2[N][S//2] if S % 2 == 0 else 0

ans = pow(3, N, mod) - (3*res1 - 3*res2)
ans %= mod
print(ans)
### BUGGY CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N=int(input())
strings=[list(str(input())) for a in range(N)]
sorteds=[]
for thing in strings:
    thing.sort()
    sorteds.append("".join(thing))
sums=0
for st in list(set(sorteds)):
    n=sorteds.count(st)
    if n!=1:
       sums=sums+combinations_count(n,2)

print(sums)



### FIXED CODE ###

import math
import collections
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N=int(input())
strings=[str(sorted(input())) for a in range(N)]
c=collections.Counter(strings)
tp=c.most_common()
sums=0
for thing in tp:
    if thing[1]!=1:
        sums=sums+combinations_count(thing[1],2)
    else:break

print(sums)
### BUGGY CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] = (l2[t] + l1[k]) % MOD
        l1 = l2
    
    ans = l1[m]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

s=input()
t=input()

s=s+s

ss=list(s)
tt=list(t)
l=len(ss)    
count=0
y=-1
ind={}
flag1=0
for x in tt:
    ind[x]=[i for i, xx in enumerate(ss) if xx == x]
    if ind[x]==[]:
        flag1=1

if flag1==0:    
    for x in tt:
        for z in ind[x]:
            if z>y:
                y=z
                flag=0
                break
            flag=1
        if flag==1:
            count+=1
            y=ind[x][0]
    #         print(count,z,y)
    ans=count*l+z+1
    print(ans)
else:
    print(-1)

### FIXED CODE ###

s = input()
t = input()
r = 0
p = 0
x = 0
for i in t:
    if s.find(i) == -1:
        print(-1)
        exit()
    if p > s.find(i):
        if s[p:].find(i) == -1:
            x += 1
            p = s.find(i) + 1
        else:
            p = p + s[p:].find(i) + 1
    else:
        p = s.find(i) + 1
print(x * len(s) + p)
### BUGGY CODE ###

n, k = map(int, input().split())
l = [int(x) for x in input().split()]

x = 1
ll = [1]
for i in l:
    x *= i
    ll.append(x)

for i in range(n-k):
    if ll[k+i]/ll[i] < ll[k+i+1]/ll[i+1]:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

n, k = map(int, input().split())
l = [int(x) for x in input().split()]

for i in range(n-k):
    if l[i] < l[k+i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
Q=int(input())
D=sum(A)
for i in range(Q):
    count=0
    B,C=map(int,input().split())
    for j in range(N):
        if A[j]==B:
            A[j]=C
            count+=1
    if B<=C:
      D=D+(C-B)*count
      print(D)
    if B>C:
      D=D+(C-B)*count
      print(D)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S = sum(A)
L = [0] * 100001
for i in A:
    L[i] += 1
Q = int(input())
for i in range(Q):
    B, C = map(int, input().split())
    S += (C - B) * L[B]
    L[C] += L[B]
    L[B] = 0
    print(S)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
ans = []
for i in range(N):
    cnt = 0
    while A[i]%2==0:
        cnt+=1
    ans.append(cnt)

print(min(ans))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
ans = []
for i in range(N):
    while A[i]%2==0:
        A[i] /=2
        cnt += 1
    ans.append(int(cnt))
    cnt = 0
        
print(min(ans))
### BUGGY CODE ###

s = list(input())
n = len(s)
a_count = 0
ans = 0
i = 0
while i < n-2:
    #print("".join(s))
    if s[i:i+3] == ['A','B','C']:
        ans +=  1
        s[i+2] = 'A'
        s[i+1] = 'C'
        s[i] = 'B'
        i -= 2
        a_count = 0
    else:
        if s[i] == 'A':
            a_count += 1
        else:
            a_count = 0
    i += 1
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
s = list(s.replace('BC','D'))
a_count = 0
ans = 0
i = 0
while i < len(s) - 1 :
    if s[i:i+2] == ['A','D']:
        ans += a_count + 1
        s[i+1] = 'A'
        s[i] = 'D'
    else:
        if s[i] == 'A':
            a_count += 1
        else:
            a_count = 0
    i += 1
print(ans)
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(map(int, input().split()))

import numpy as np
n,k,q = mi()
a=np.array([int(input()) for i in range(q)])

point = np.array([k for i in range(n)])

for i in range(q):
    point -= 1
    b = a[i]-1
    point[b] += 1

for i in range(n):
    if point[i]>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(map(int, input().split()))

import numpy as np
n,k,q = mi()
a=[int(input()) for i in range(q)]

point = np.array([k-q for i in range(n)])

for i in a:
    point[i-1] += 1

ans = np.where(point>0, 'Yes', 'No')

print('\n'.join(ans))
### BUGGY CODE ###

from math import gcd
import itertools

def calc(a,b,c):
    x=gcd(a,b)
    y=gcd(x,c)
    return y

n=int(input())

A=list(itertools.product(range(1,n+1), repeat=3))

D={}
for i in A:
    mat=tuple(sorted(i))
    if mat in D:
        D[mat]+=1
    else:
        D[mat]=1

ans=0
for a,b,c in D:
    ans+=calc(a,b,c)*D[(a,b,c)]
print(ans)


### FIXED CODE ###

from math import gcd
import itertools

def calc(a,b,c):
    x=gcd(a,b)
    y=gcd(x,c)
    return y

n=int(input())
A=list(itertools.combinations_with_replacement(range(1,n+1), 3))

ans=0
for a,b,c in A:
    if a==b==c:
        ans+=calc(a,b,c)
    elif a!=b and a!=c and b!=c:
        ans+=calc(a,b,c)*6
    else:
        ans+=calc(a,b,c)*3
print(ans)
### BUGGY CODE ###

n, W = map(int, input().split())
dp = [[0 for _ in range(W + 1)] for i in range (n + 1)]
for i in range(1, n + 1):
    w, v = map(int, input().split())
    for j in range(1, W + 1):
        if w > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
print(dp[-1][-1])

### FIXED CODE ###

n, W = map(int, input().split())
dp = [[0 for _ in range(W + 1)] for i in range (n + 1)]
for i in range(1, n + 1):
    w, v = map(int, input().split())
    for j in range(1, W + 1):
        if w > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
print(dp[-1][-1])
### BUGGY CODE ###

K=int(input())

Ans=0
import math

for i in range(K):
    for j in range(K):
        for k in range(K):
            temp=math.gcd(i+1,j+1)
            Ans+=math.gcd(temp,k+1)

print(Ans)


### FIXED CODE ###

K=int(input())+1

Ans=0
from math import gcd
for i in range(1,K):
    for j in range(1,K):
        tempA=gcd(i,j)
        for k in range(1,K):
            Ans+=gcd(tempA,k)
            
print(Ans)
### BUGGY CODE ###

#023_B
n = int(input())
s = [input() * 2 for _ in range(n)]
ans = 0
for b in range(0, n):
    flg = True
    for i in range(n):
        for j in range(n):
            if s[i][b+j] != s[j][b+i]:
                flg = False
                break
    if flg:
        ans += 1

print(ans * n)

### FIXED CODE ###

#023_B
n = int(input())
s = [input() * 2 for _ in range(n)]
ans = 0
for b in range(0, n):
    flg = True
    for i in range(n):
        for j in range(n):
            if s[i][b+j] != s[j][b+i]:
                flg = False
                break
    if flg:
        ans += 1

print(ans * n)
### BUGGY CODE ###

S=input()
l=len(S)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1

for i in range(l):
  if S[i]=='?':
    for k in range(13): 
      for j in range(10):      
        dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
  else:
    for k in range(13):
      dp[i+1][(k*10 + int(S[i]))%13]+=dp[i][k]%mod
      
print(dp[-1][5]%mod)

### FIXED CODE ###

S=input()
l=len(S)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1

for i in range(l):
  if S[i]=='?':
    for k in range(13): 
      for j in range(10):      
        dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
  else:
    for k in range(13):
      dp[i+1][(k*10 + int(S[i]))%13]+=dp[i][k]%mod
      
print(dp[-1][5]%mod)
### BUGGY CODE ###

from bisect import bisect
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
a.sort()
b.sort()
cnt = 1
for i in range(1,n*m+1)[::-1]:
    if i in a:
        if i in b:
            cnt *= 1
        else:
            cnt *= m-bisect(b,i)
            cnt %= 1000000007
    else:
        if i in b:
            cnt *= n-bisect(a,i)
            cnt %= 1000000007
        else:
            cnt *= (n - bisect(a,i))*(m - bisect(b,i)) - (n*m - i)
            cnt %= 1000000007
if len(a) != len(set(a)) or len(b) != len(set(b)) :
    cnt = 0
print(cnt)


### FIXED CODE ###

from bisect import bisect
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
a.append(0)
b.append(0)
a.sort()
b.sort()
ia = 0
ib = 0
cnt = 1
for i in range(1,n*m+1)[::-1]:
    if i == a[-1]:
        if i == b[-1]:
            cnt *= 1
            a.pop(-1)
            b.pop(-1)
            ia += 1
            ib += 1
        else:
            cnt *= ib
            a.pop(-1)
            cnt %= 1000000007
            ia += 1
    else:
        if i == b[-1]:
            cnt *= ia
            b.pop(-1)
            cnt %= 1000000007
            ib += 1
        else:
            cnt *= ia*ib - (n*m - i)
            cnt %= 1000000007

print(cnt)