Harryxun/stf_run huggingface dataset:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
# N = 9
# AB = [[1, 2], [2, 3], [9, 8], [8, 3], [3, 4], [4, 5], [3, 6], [6, 7]]
if N == 2:
    print(1, 2)
if N == 3:
    print(1, 2, 3)

x1 = set()
x2 = set()
x3 = set()

for i in range(1, N + 1):
    if i % 3 == 1:
        x1.add(i)
    elif i % 3 == 2:
        x2.add(i)
    else:
        x3.add(i)
x = [x1, x2, x3]

result = {}


class Node:
    def __init__(self, v):
        self.linked = set()
        self.v = v

    def add_node(self, node):
        self.linked.add(node)

    def set_rank(self, parent, rank):
        self.rank = rank
        if parent == None:
            result[self.v] = x1.pop()
        else:
            if x[(result[parent.v] + 1) % 3]:
                result[self.v] = x[(result[parent.v] + 1) % 3].pop()
            elif x1:
                result[self.v] =  x1.pop()
            elif x2:
                result[self.v] =  x2.pop()
            else:
                result[self.v] =  x3.pop()
        for node in self.linked:
            if node == parent:
                continue
            node.set_rank(parent=self, rank=rank + 1)

    def __repr__(self):
        return '{}'.format(self.rank)


nodes = {v: Node(v) for v in range(1, N + 1)}
for a, b in AB:
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

# usokaihou
root = nodes[1]
root.set_rank(None, 0)
print(' '.join(str(result[i]) for i in range(1, N + 1)))

exit()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]


class Tree:
    def __init__(self, v):
        self.v = v
        self.neighbors = []

    def set_rank(self, rank, parent):
        self.rank = rank
        for neighbor in self.neighbors:
            if neighbor is parent:
                continue
            neighbor.set_rank(rank=rank + 1, parent=self)


trees = {i: Tree(i) for i in range(1, N + 1)}

for a, b in AB:
    trees[a].neighbors.append(trees[b])
    trees[b].neighbors.append(trees[a])
try:
    trees[1].set_rank(1, None)
except:
    print(-1)
    exit()

group0 = [node.v for node in trees.values() if node.rank % 2 == 0]
group1 = [node.v for node in trees.values() if node.rank % 2]
x = [set(), set(), set()]
for i in range(1, N + 1):
    x[i % 3].add(i)
if len(group1) < len(group0):
    group1, group0 = group0, group1
result = {}
if len(group0) <= len(x[0]):
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    y = x[0] | x[1] | x[2]
    while group1 and y:
        result[group1.pop()] = y.pop()
else:
    while x[2] and group0:
        result[group0.pop()] = x[2].pop()
    while x[1] and group1:
        result[group1.pop()] = x[1].pop()
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    while group1 and x[0]:
        result[group1.pop()] = x[0].pop()
    if group0 or group1:
        print(-1)
        exit()

print(' '.join(str(result[i]) for i in range(1, N + 1)))
a.b.c.d.e.k=map(int,input().split())
if abs(a-b)>=k and abs(a-c)>=k and abs(a-d)>=k and abs(a-e)>=k and abs(b-c)>=k and abs(b-d)>=k and abs(b-e)>=k abs(c-d)>=k and abs(c-e)>=k and abs(d-e)>=k:
  print("Yey!")
else:
  print(":(")

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

if e - a > k:
    print(":(")
elif e - b > k:
    print(":(")
elif e - c > k:
    print(":(")
elif e - d > k:
    print(":(")
else:
    print("Yay!")
import sys
input = sys.stdin.readline

N = int(input())
X = [int(x) for x in input().split()]
MAX = max(X)
res = []
for a in range(1, MAX):
  total = 0
  for x in X:
    kyori = (x - a) * (x - a)
    total += kyori
  res.append(total)
print(min(res))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
X = [int(x) for x in input().split()]
P = int(sum(X) / N + 0.5)
total = 0
for x in X:
  kyori = (x - P) * (x - P)
  total += kyori
print(total)
import sys
input = sys.stdin.readline
s = 0
N = int(input())
for i in range(1, int(N/2)):
    if N%i == 0 and i > s:
        s = i
print(s+(N//s)-2)

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = 0
N = int(input())
for i in range(1, int(N**(1/2))+1):
    if N%i == 0 and i > s:
        s = i
print(s+(N//s)-2)
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
L = int(input())
k = 0
while a[-1] // (L * pow(2, k)): k += 1
e = [[0] * (k + 1) for _ in range(N)]
for i in range(N):
  t = L + a[i]
  ok = i
  ng = N
  while ng - ok > 1:
    m = (ok + ng) // 2
    if a[m] <= t: ok = m
    else: ng = m
  e[i][0] = ok
for j in range(len(e[i]) - 1):
  for i in range(N):
    x = e[i][j]
    e[i][j + 1] = e[x][j]
print(e)

def doubling(u, v):
  if u == v: return 0
  x = bl(e[u], v)
  x = max(0, x - (e[u][x] == N - 1))
  #print(u, v, x)
  return doubling(e[u][x], v) + pow(2, x)

Q = int(input())
for _ in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  if x > y: x, y = y, x
  print(doubling(x, y))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
L = int(input())
k = 1
while a[-1] // (L * pow(2, k)): k += 1
e = [[0] * k for _ in range(N)]
for i in range(N):
  t = L + a[i]
  ok = i
  ng = N
  while ng - ok > 1:
    m = (ok + ng) // 2
    if a[m] <= t: ok = m
    else: ng = m
  e[i][0] = ok
for j in range(len(e[i]) - 1):
  for i in range(N):
    x = e[i][j]
    e[i][j + 1] = e[x][j]
#print(e)

def doubling(u, v):
  if u == v: return 0
  ok = -1
  ng = len(e[u])
  while ng - ok > 1:
    m = (ok + ng) // 2
    if e[u][m] < v: ok = m
    else: ng = m
  if ok < 0: return 1
  return doubling(e[u][ok], v) + pow(2, ok)

Q = int(input())
for _ in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  if x > y: x, y = y, x
  print(doubling(x, y))
Dist = abs(y1-y2)**2+abs(x1-x2)**2
dist = Dist**0.5
if x2 >= x1 and y2 >= y1:
  x3=x2-abs(y2-y1)
  x4=x1-abs(y2-y1)
  y3=y2+abs(x2-x1)
  y4=y1+abs(x2-x1)
elif x2 < x1 and y2 >= y1:
  x3=x2-abs(y2-y1)
  x4=x1-abs(y2-y1)
  y3=y2-abs(x2-x1)
  y4=y1-abs(x2-x1)
elif x2 < x1 and y1 >= y2:
  x3=x2+abs(y2-y1)
  x4=x1+abs(y2-y1)
  y3=y2-abs(x2-x1)
  y4=y1-abs(x2-x1)
else:
  x3=x2+abs(y2-y1)
  x4=x1+abs(y2-y1)
  y3=y2+abs(x2-x1)
  y4=y1+abs(x2-x1)
print(x3,y3,x4,y4)

### FIXED CODE ###

x1,y1,x2,y2=map(int,input().split())
if x2 >= x1 and y2 >= y1:
  x3=x2-abs(y2-y1)
  x4=x1-abs(y2-y1)
  y3=y2+abs(x2-x1)
  y4=y1+abs(x2-x1)
elif x2 < x1 and y2 >= y1:
  x3=x2-abs(y2-y1)
  x4=x1-abs(y2-y1)
  y3=y2-abs(x2-x1)
  y4=y1-abs(x2-x1)
elif x2 < x1 and y1 >= y2:
  x3=x2+abs(y2-y1)
  x4=x1+abs(y2-y1)
  y3=y2-abs(x2-x1)
  y4=y1-abs(x2-x1)
else:
  x3=x2+abs(y2-y1)
  x4=x1+abs(y2-y1)
  y3=y2+abs(x2-x1)
  y4=y1+abs(x2-x1)
print(x3,y3,x4,y4)
import numpy as np

D = int(input())
c = np.array( list(map(int, input().split())) )
#
s = [[] for i in range(D)]
for i in range(D):
  s[i] = np.array( list(map(int, input().split())) )
#
v = 0
cc =  np.array( [0]*26 )
last = np.array( [-1]*26 )
for d in range(D):
  cc += c
  av = s[d] - sum( cc ) + cc
  av2 = av + cc*(D-d-1) + c*(D-d-1)(D-d)//2
  m = max(av2)
  for t in range(26):
    if av2[t] == m:
      cc[t] = 0
      v += av[t]
      print(t+1)
      break
#
#print( v )


### FIXED CODE ###

import numpy as np

D = int(input())
c = np.array( list(map(int, input().split())) )
s = [[] for i in range(365)]
for i in range(D):
  s[i] = np.array( list(map(int, input().split())) )
#
last = np.array( [-1]*26 )
av = np.array( [0]*26 )
id = np.identity(4,dtype=int)

v = 0
for d in range(D):
  av = s[d] - sum( c*(d-last) ) + c*(d-last) 
  m = max(av)
  for t in range(26):
    if av[t] == m:
      last[t] = d
      v += av[t]
      print(t+1)
      break
#
a,b,c = map(int, input().split())
print "Yes" if a<b and b<c else "No"


### FIXED CODE ###

a,b,c = map(int, input().split())
print("Yes" if a<b and b<c else "No")
n=int(input())
a = list(map(int, input().split()))
ans=1

if 0 in a :
  ans=0
else:
  for i in range(n):
    if len(str(ans))>=19:
      ans='-1'
      break
    else:
      ans*=a[i]
if ans>10**18:
  ans='-1'
print(ans)

### FIXED CODE ###

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

if 0 in a :
  ans=0
else:
  for i in range(n):
    if len(str(ans))>=19:
      ans='-1'
      break
    else:
      ans*=a[i]
if ans==1000000000000000000:
  ans=1000000000000000000
elif len(str(ans))>=19:
  ans=-1
print(ans)
N = int(input())
S= input()
count = 0
R,G,B = [],[],[]
r = S.count('R')
g = S.count('G')
b = S.count('B') 
for i in range(N):
    for j in range(i+1,N+1):
        if S[i] != S[j] and S[2*j-i] != S[i] and S[2*j-i] != S[j]:
            sub += 1
ans = r*g*b -sub
print(ans)
       

### FIXED CODE ###

N = int(input())
S= input()
sub = 0
R,G,B = [],[],[]
r = S.count('R')
g = S.count('G')
b = S.count('B') 
for i in range(N):
    for j in range(i+1,N):
        if 2*j-i > N-1:
            break
        if S[i] != S[j] and S[2*j-i] != S[i] and S[2*j-i] != S[j]:
            sub += 1
ans = r*g*b -sub
print(ans)
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    if a % 2 == 0:
        if a % 3 == 0 or a % 5 == 0:
            print("APPROVED")
    else:
        print("DENIED")



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
flg = True
for i in range(n):
    if a[i] % 2 == 0:
        if a[i] % 3 == 0 or a[i] % 5 == 0:
            pass
        else:
            flg = False
            break

if flg:
    print("APPROVED")
else:
    print("DENIED")
from math import gcd


def lcm(x, y):
    return (x*y) // gcd(x, y)


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

print(lcm(a, b))


### FIXED CODE ###

import fractions


def lcm(x, y):
    return (x*y) // fractions.gcd(x, y)


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

print(lcm(a, b))
N = int(input().strip())

points = []

for i in range(0,N):
    points.append(list(map(int, input().strip().split())))

for cx in range(0,101):
    for cy in range(0,101):
        H = (points[0][2] + abs(points[0][0] - cx) + abs(points[0][1] - cy))
        if all([points[i][2] == max(H - (abs(points[i][0] - cx) + abs(points[i][1] - cy)),0) for i in range(1,N)]):
            res = [cx,cy,H]
            break


print(res[0],res[1],res[2])

### FIXED CODE ###

N = int(input().strip())

points = []

for i in range(0,N):
    points.append(list(map(int, input().strip().split())))

for cx in range(0,101):
    for cy in range(0,101):
        for p in points:
            if p[2] > 0:
                target = p
                break
        H = (target[2] + abs(target[0] - cx) + abs(target[1] - cy))
        if all([points[i][2] == max(H - (abs(points[i][0] - cx) + abs(points[i][1] - cy)),0) for i in range(0,N)]):
            res = [cx,cy,H]
            break


print(res[0],res[1],res[2])
print('x'*len(input())

### FIXED CODE ###

S = input()
print('x'*len(S))
H, W, M = map(int, input().split())
S = [[0]*W for _ in range(H)]
dich = {i: 0 for i in range(H)}
dicw = {i: 0 for i in range(W)}
l = []
for _ in range(M):
  h, w = map(lambda x: int(x)-1, input().split())
  dich[h] += 1
  dicw[w] += 1
  l.append((h, w))

maxh = max(dich.values())
maxw = max(dicw.values())
cnt = 0

ch = sum([1 for i in dich.values() if i == maxh])
cw = sum([1 for i in dicw.values() if i == maxw])
for y, x in l:
  if dich[y] == maxh and dicw[x] == maxw:
    cnt += 1

ans = maxh+maxw
if cnt == ch*cw:
  ans -= 1

print(ans)    


### FIXED CODE ###

ans=0

h,w,m=map(int,input().split())
d=list()
from collections import defaultdict
r=defaultdict(int)
c=defaultdict(int)
r=[0]*(h+1)
c=[0]*(w+1)
for i in range(m):
  a,b=map(int,input().split())
  d+=(a,b),
  r[a]+=1
  c[b]+=1
R=max(r)
C=max(c)

x=0
nr=r.count(R)
nc=c.count(C)
for i in range(m):
    a,b=d[i]
    if r[a]==R and c[b]==C:
        x+=1

ans=R+C
if x==nr*nc:
    ans-=1
print(ans)
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a_max = max(a)
ind_M = a.index(a_max)
oth = max(max(a[:ind_M]), max(a[ind_M+1:]))
for i in range(n):
    if i != ind_M:
        print(a_max)
    else:
        print(oth)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a_max = max(a)
ind_M = a.index(a_max)
tmpl = a
tmpl.pop(ind_M)
for i in range(n):
    if i != ind_M:
        print(a_max)
    else:
        print(max(tmpl))
s = int(input())
v = 10 ** 9
x1 = 0
y1 = 0
x2 = v
y2 = 1
x3 = (v - s % v) % v
y3 = (s + x) // v
print(x1, y1, x2, y2, x3, y3)

### FIXED CODE ###

s = int(input())
v = 10 ** 9
x1 = 0
y1 = 0
x2 = v
y2 = 1
x3 = (v - s % v) % v
y3 = (s + x3) // v
print(x1, y1, x2, y2, x3, y3)
n,m,q=map(int,input().split())
abcd=[]
for _ in range(q):
	a,b,c,d=map(int,input().split())
	abcd.append((a,b,c,d))
ans=0
p=[]
sys.setrecursionlimit(10**6)
def dfs(x):
	if len(x)==n:
		p.append(x)
	else:
		for i in range(m-x[-1]+1):
			dfs(x+[x[-1]+i])
dfs([1])
# import itertools
# p=itertools.combinations_with_replacement(range(1,m+1),n)
for x in p:
	r=0
	for i in range(q):
		if x[abcd[i][1]-1]-x[abcd[i][0]-1]==abcd[i][2]:
			r+=abcd[i][3]
	ans=max(ans,r)
print(ans)

### FIXED CODE ###

n,m,q=map(int,input().split())
abcd=[]
for _ in range(q):
	a,b,c,d=map(int,input().split())
	abcd.append((a,b,c,d))
ans=0
import itertools
p=itertools.combinations_with_replacement(range(1,m+1),n)
for x in p:
	r=0
	for i in range(q):
		if x[abcd[i][1]-1]-x[abcd[i][0]-1]==abcd[i][2]:
			r+=abcd[i][3]
	ans=max(ans,r)
print(ans)
N=int(input())
S=list(input.split())
if "Y" in S:
  print("Four")
else:
  print("Three")

### FIXED CODE ###

N=int(input())
S=list(input().split())
if "Y" in S:
  print("Four")
else:
  print("Three")
from math import gcd
n, k = map(int, input().split())
a = list(map(int, input().split()))
g = a[0]
for x in a:
    g = gcd(g, x)
print(("IMPOSSIBLE", "POSSIBLE")[int(k <= max(a) and k % g == 0)])


### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

n, k = map(int, input().split())
a = list(map(int, input().split()))
g = a[0]
for x in a:
    g = gcd(g, x)
print(("IMPOSSIBLE", "POSSIBLE")[k <= max(a) and k % g == 0])
import fractions
A,B=map(int,input().split())
print(int(A*B/fractions.gcd(A,B)))

### FIXED CODE ###

from math import sqrt
from decimal import Decimal
ans = [1,2,3]
A,B=int(input()),int(input())
ans.remove(A)
ans.remove(B)
print(ans[0])
from collections import deque
from collections import namedtuple

N = int(input())
A = [int(i) for i in input().split()]
Prog = namedtuple("Prog","p,c")
d = deque([(deque(A),0)])
ans = 0
while(len(d)>0):
    tmp = d.pop()
    tmp2 = deque()
    for i in gen(tmp[0]):
        tmp2.appendleft(i.p)
    tmp2.pop()
    if len(tmp2) < 1:
        if ans < tmp[1]:
            ans = tmp[1]
    else:
        for i in tmp2:
            d.appendleft((i,tmp[1]+1))
print(ans)

### FIXED CODE ###

from collections import deque
N = int(input())
A = [int(i) for i in input().split()]

d = deque(A)
c = 0
while(len(d)>0):
    tmp = d.pop()
    if tmp%2==0:
        c+=1
        d.append(tmp//2)
print(c)
import sys
X, Y = map(int, input().split())
for i in range(X+1):
  j = X - i
  if 2*i+4*j == Y:
    print('Yes')
    sys.exit()
print('No")

### FIXED CODE ###

import sys
X, Y = map(int, input().split())
for i in range(X+1):
  j = X - i
  if 2*i+4*j == Y:
    print('Yes')
    sys.exit()
print('No')
import sys
import numpy as np
import copy
from itertools import accumulate
input=sys.stdin.readline
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    ans = copy.deepcopy(A)
    for _ in range(K):
        cumsum = [0]*N
        for i,a in enumerate(ans):
            l = max(0,i-a)
            r = min(N-1,i+a)
            cumsum[l] += 1
            if r+1 < N:
                cumsum[r+1] -= 1
        ans = list(accumulate(cumsum))
        if ans[0] == N:
            break
    print(*ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import copy
from itertools import accumulate
input=sys.stdin.readline
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    ans = copy.deepcopy(A)
    for _ in range(K):
        cumsum = [0]*N
        for i,a in enumerate(ans):
            l = max(0,i-a)
            r = min(N-1,i+a)
            cumsum[l] += 1
            if r+1 < N:
                cumsum[r+1] -= 1
        ans = list(accumulate(cumsum))
        if ans[0] == N:
            break
    print(*ans)
    
if __name__ == '__main__':
    main()
a, b = input().split()
print("even" if a * b % 2 == 0 else "odd")

### FIXED CODE ###

a, b = map(int, (input().split()))
print("Even" if a * b % 2 == 0 else "Odd")
w, h, n = map(int, input().split())
xya = [list(map(int, input().split())) for i in range(n)]
x,y,a=[],[],[]
for z in xya:
    x.append(z[0])
    y.append(z[1])
    a.append(z[2])
pp = np.array([[1]*w]*h)
for i in range(n):
    if a[i]==1:
        pp[:, :x[i]]=0
    if a[i]==2:
        pp[:, x[i]:]=0
    if a[i]==3:
        pp[(h-y[i]):, :]=0
    if a[i]==4:
        pp[:(h-y[i]), :]=0
print(sum(sum(pp)))

### FIXED CODE ###

import numpy as np
w, h, n = map(int, input().split())
xya = [list(map(int, input().split())) for i in range(n)]
x,y,a=[],[],[]
for z in xya:
    x.append(z[0])
    y.append(z[1])
    a.append(z[2])
pp = np.array([[1]*w]*h)
for i in range(n):
    if a[i]==1:
        pp[:, :x[i]]=0
    if a[i]==2:
        pp[:, x[i]:]=0
    if a[i]==3:
        pp[(h-y[i]):, :]=0
    if a[i]==4:
        pp[:(h-y[i]), :]=0
print(sum(sum(pp)))
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))

    pmod={}
    cummod=0
    for num in a:
        cummod+=num
        cummod%=m
        if cummod not in pmod:
            pmod[cummod]=1
        else:
            pmod[cummod]+=1
    
    ans=pmod[0]
    for i in pmod:
        if pmod[i] >=2 :
            ans+=pmod[i]*(pmod[i]-1)//2
    
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))

    pmod={}
    cummod=0
    for num in a:
        cummod+=num
        cummod%=m
        if cummod not in pmod:
            pmod[cummod]=1
        else:
            pmod[cummod]+=1
    
    if 0 in pmod:
        ans=pmod[0]
    else:
        ans=0
        
    for i in pmod:
        if pmod[i] >=2 :
            ans+=pmod[i]*(pmod[i]-1)//2
    
    print(ans)

if __name__=='__main__':
    main()
s=list(input())

print(s[0]+str(len(s-2))+s[len(s)-1])

### FIXED CODE ###

s=list(input())

print(s[0]+str(len(s)-2)+s[len(s)-1])
N = int(input())
Aj = list(map(int, input()split()))

ans = 1
ng = false
max = 10**18
for A in Aj:
	if A == 0:
		ans = 0
		break
	if ans*A > max:
		ans *= A
print(ans)

### FIXED CODE ###

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

ans = 1
ng = False
max = 10**18
for A in Aj:
	if A == 0:
		ans = 0
		break
	if ng or ans*A > max:
		ans = -1
		ng = True
	else:
		ans *= A
print(ans)
H,W=map(int,input().split())
hlen = list(map(int,input().split()))
wlen =	list(map(int,input().split()))
hlen.sort(reverse=True)
wlen.sort(reverse=True)
hhlen =[0 for _ in range(H*W+1)]
wwlen =[0 for _ in range(H*W+1)]
for x,xx in zip([hlen,wlen],[hhlen,wwlen]):
	c = 1
	for y in x:
		if xx[y] != 0:
			print(0)
			exit()
		else:
			xx[y] = c
			c += 1

def Count(x,l):
	ret = 0
	for ll in l[x:]:
		if ll > 0:
			return ll

m = max(hlen[0],wlen[0])
count = 1
for num in range(1,H*W+1)[::-1]:
	flagh = 0
	flagw = 0
	if hhlen[num]:
		flagh = 1
	if wwlen[num]:
		flagw = 1
	if flagh and flagw:
		count *= 1
	elif flagh:
		count *= Count(num,wwlen)
	elif flagw:
		count *= Count(num,hhlen)
	else:
		count *= Count(num,hhlen)*Count(num,wwlen) - (m-num)
	#print(num,flagh,flagw,count)
	count %= (10**9+7)
print(count % (10**9+7))

### FIXED CODE ###

H,W=map(int,input().split())
hlen = list(map(int,input().split()))
wlen =	list(map(int,input().split()))
hlen.sort(reverse=True)
wlen.sort(reverse=True)
hlen.append(0)
wlen.append(0)

m = H*W
count = 1
h=0
w=0
for num in range(1,H*W+1)[::-1]:
	if hlen[h] == num and wlen[w] == num:
		count *= 1
		h += 1
		w += 1
	elif hlen[h] == num:
		count *= w
		h += 1
	elif wlen[w] == num:
		count *= h
		w += 1
	else:
		count *= h*w - (m-num)
	#print(num,flagh,flagw,count)
	count %= (10**9+7)
print(count)
import math
a,b,x = map(int,input().split())
v = a **2 * b
h = 0
ans = 0
if(x > v // 2):
    ans = 90 - math.degrees(math.atan(a ** 3 / ( 2 * (v - x))))
else:
    ans = 90 - math.degrees(math.atan(x / (a * b **2 // 2)))
print(ans)

### FIXED CODE ###

import math
a,b,x = map(int,input().split())
v = a **2 * b
h = 0
ans = 0
if v == x:
    ans = 0
elif(x > v // 2):
    ans = 90 - math.degrees(math.atan(a ** 3 / ( 2 * (v - x))))
else:
    ans = 90 - math.degrees(math.atan(x / (a * b **2 // 2)))
print(ans)
n=int(input())
l=list(map(int,input().split()))
ans=1
mod=1000000007
me=[0,0,0]
now=3
for x in l:
  if x==0:
    ans*now
    now-=1
    if now<0:
      print(0)
      quit()
    me[-now]=1
  else:
    a=len([i for i, y in enumerate(me) if y == x])
    if a>3:
      print(0)
      quit()
    ans=ans*a%mod    
    me[me.index(x)]+=1
if now==0:
  print(6*ans%mod)
else:
  print(3*ans%mod)

### FIXED CODE ###

n=int(input())
mod=1000000007
l=list(map(int,input().split()))
me=[3]+[0]*2*n
ans=1
for x in l:
  ans=ans*me[x]%mod
  me[x]-=1
  me[x+1]+=1
print(ans)
A = [int(input()) for i in range(5)]
K = input()

lenge = 0

for i in range(A):
  for j in range(A):
    if A[i] - A[j] > K:
      lenge += 1
      
if lenge == 0:
  print(":(")
else :
  print("Yay!")


### FIXED CODE ###

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

lenge = 0

for i in range(5):
  for j in range(5):
    if A[i] - A[j] > K:
      lenge += 1
      
if lenge > 0:
  print(":(")
else :
  print("Yay!")
n,k,s = map(int,input().split())

u = []
if n == k:
    print(' '.join(str,[s]*n))
else:
    if s%2==0:
        for i in range(k+1):
            u.append(int(s/2))
        for i in range(n-k-1):
            u.append(10**9-1)
    else:
        if s==1:
            for i in range(k):
                u.append(1)
            for i in range(n-k-1):
                u.append(10**9)
        else:
            if k%2==0:
                u.append(int((s-1)/2))
                for i in range(int(k/2)):
                    u.append(int((s+1)/2))
                    u.append(int((s-1)/2))    
                for i in range(n-k+1):
                    u.append(10**9)
            else:
                for i in range(int(k/2)):
                    u.append(int((s+1)/2))
                    u.append(int((s-1)/2))  
                for i in range(n-k+1):
                    u.append(10**9)
print(' '.join(map(str,u)))

### FIXED CODE ###

n,k,s = map(int,input().split())

u = []
if n == k:
    for i in range(n):
        u.append(s)
else:
    if s%2==0:
        for i in range(k+1):
            u.append(int(s/2))
        for i in range(n-k-1):
            u.append(10**9-1)
    else:
        if s==1:
            for i in range(k):
                u.append(1)
            for i in range(n-k):
                u.append(10**9)
        else:
            if k%2==0:
                u.append(int((s-1)/2))
                for i in range(int(k/2)):
                    u.append(int((s+1)/2))
                    u.append(int((s-1)/2))    
                for i in range(n-k-1):
                    u.append(10**9)
            else:
                for i in range(int((k+1)/2)):
                    u.append(int((s+1)/2))
                    u.append(int((s-1)/2))  
                for i in range(n-k-1):
                    u.append(10**9)
print(' '.join(map(str,u)))