Harryxun/stf_run huggingface dataset:
n, k = map(long, input().split())
a = list(map(long, input().split()))
mod = 10**9 + 7
ans = 0
fflag = 0
bflag = 0

for i in range(n):
    for j in range(n):
        if i > j:
            if a[i] > a[j]:
                fflag += 1
        if i < j:
            if a[i] > a[j]:
                bflag += 1

ans = (long((fflag+bflag)*k*(k+1)/2) - fflag*k)%mod
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0
fflag = 0
bflag = 0

for i in range(n):
    for j in range(n):
        if i > j:
            if a[i] > a[j]:
                fflag += 1
        elif i < j:
            if a[i] > a[j]:
                bflag += 1

ans = ((fflag+bflag)*k*(k+1)//2 - fflag*k)%mod
print(ans)
R, G, B, N = map(int, input().split())
R, G, B = sorted([R, G, B], reverse=True)
maxR = N // R
ans = 0
if R == 1:
    ans += (N+2)(N+1) // 2
    print(ans)
    quit()

for r in range(maxR+1):
    if r * R == N:
        ans += 1
        continue
    n = N - r * R
    maxG = n // G
    for g in range(maxG+1):
        if g * G == n:
            ans += 1
            continue
        nn = n - g * G
        maxB = nn // B
        for b in range(maxB+1):
            if b * B == nn:
                ans += 1

print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
R, G, B = sorted([R, G, B], reverse=True)
maxR = N // R
ans = 0
if R == 1:
    ans = (N+2)*(N+1) // 2
    print(ans)
    quit()

for r in range(maxR+1):
    if r * R == N:
        ans += 1
        continue
    n = N - r * R
    maxG = n // G
    for g in range(maxG+1):
        if g * G == n:
            ans += 1
            continue
        nn = n - g * G
        maxB = nn // B
        for b in range(maxB+1):
            if b * B == nn:
                ans += 1

print(ans)
n = int(input())
s = input()
print(max(len(set(s[:i])&set(s[i:]) for i in range(n))))

### FIXED CODE ###

N = int(input())
S = input()
max = 0
for i in range(1, N-1):
  X = set(S[0:i])
  Y = set(S[i:N])
  if max < len(X&Y):
    max = len(X&Y)
print(max)
import numpy 
x = int(input())
max = 10**9+1
flag = False
for i in range(1,max):
    if x%i == 0:
        for j in range(-i,i+1): 
            if (numpy.power(i-j,5) - numpy.power(j,5)) == x:
                print(str(i-j)+" "+str(j))
                flag = True
                break
    if flag:
        break

### FIXED CODE ###

s = input()

if s == "ABC":
    print("ARC")
else:
    print("ABC")
a, b, c, d = map(int, input().split())

while a>0 and c>0:
  c -= b
  a -= d
  
  

if a>>o:
  print("Yes")
  
else:
  print("No")
  
  


### FIXED CODE ###

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

while a>0 and c>0:
  c -= b
  a -= d
  
  
if c<=0:
  print("Yes")
  
else:
  print("No")
n, m = map(int, input().split())
a = list(map(lambda x:int(x) // 2, input().split()))

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
	return a * b // gcd (a, b)

temp = lcm(a[0], a[1])
if (temp // a[0]) % 2 == 0 or (temp // a[1]) % 2 == 0:
    print(0)
    exit()

if n > 2:
    for y in a[2:]:
        temp = lcm(temp, y)
        if (temp // y) % 2 == 0 or temp > m:
            print(0)
            exit()

ans = m // temp
print(ans - ans // 2)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(lambda x:int(x) // 2, input().split()))

a = sorted(list(set(a)))

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
	return a * b // gcd (a, b)

if len(a) == 1:
    ans = m // a[0]
    print(ans - ans // 2)
    exit()

temp = lcm(a[0], a[1])
if (temp // a[0]) % 2 == 0 or (temp // a[1]) % 2 == 0:
    print(0)
    exit()

for y in a[2:]:
    temp = lcm(temp, y)
    if (temp // y) % 2 == 0 or temp > m:
        print(0)
        exit()

ans = m // temp
print(ans - ans // 2)
import bisect
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
zero = bisect.bisect_left(a,0)
Z = min(n-zero,zero,k)
cnt = min(-sum(a[Z-k:zero]),sum(a[zero:zero+Z]))
for i in range(1,k):
    if cnt > -2*a[zero-i]+a[zero+k-i-1]:
        cnt = -2*a[zero-i]+a[zero+k-i-1]
    else:
        break
for i in range(1,k):
    if cnt > -a[zero-k+i]+2*a[zero+i-1]:
        cnt = -a[zero-k+i]+2*a[zero+i-1]
    else:
        break

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
c=10**10
for i in range(n-k+1):
    c=min(c,-a[i]+a[i+k-1]\
          +min(abs(a[i]),abs(a[i+k-1])))
print(c)
# coding: utf-8
import collections

n=int(input())
d=list(map(int,input().split()))
c = collections.Counter(d)
ans = 1
m=max(d)


for i in range(m):
    ans*=c[i]**c[i+1]
    ans = ans%998244353

if c[0]!=1:
    ans=0
if D[0] != 0:
    ans = 0

# print(c)
print(ans)


### FIXED CODE ###

# coding: utf-8
import collections

n=int(input())
d=list(map(int,input().split()))
c = collections.Counter(d)
ans = 1
m=max(d)


for i in range(m):
    ans*=c[i]**c[i+1]
    ans = ans%998244353

if c[0]!=1:
    ans=0
if d[0] != 0:
    ans = 0

# print(c)
print(ans)
n,m = map(int,input().split())
path = {}
for i in range(m):
    a,b = map(int,input().split())
    if a not in path:
        path[a] = [b]
    else:
        path[a].append(b)

ns = []
for p in path[1]:
    ns.append(p)

flag = False
for mid in ns:
    if n in path[mid]:
        flag = True
        break

if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
        

### FIXED CODE ###

n,m = map(int,input().split())
path = {}
for i in range(m):
    a,b = map(int,input().split())
    if a not in path:
        path[a] = [b]
    else:
        path[a].append(b)

ns = []
if 1 in path:
    for p in path[1]:
        ns.append(p)

    flag = False
    for mid in ns:
        if mid in path:
            if n in path[mid]:
                flag = True
                break

    if flag:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

else:
    print("IMPOSSIBLE")
a, b, c, d = map(input().split())

ab = a - b
bc = b - c
ac = a - c

if ab <= d and bc <= d or ac <= d:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

if abs(a-b) <= d and abs(b-c) <= d or abs(a-c) <= d:
    print('Yes')
else:
    print('No')
import math
from operator import mul
from functools import reduce
n, a, b = map(int, input().split())
s=0
mod = pow(10, 9) + 7
def combinations_count(n, r):
    #return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
if n==2:
    print('0')
a=combinations_count(n, a)

b=combinations_count(n, b)
else:
    print((pow(2, n, mod) -1 -a -b) % mod)

### FIXED CODE ###


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n, a, b = map(int, input().split())
mod = pow(10, 9) + 7
 
def comb(N, x):
    numerator = 1
    for i in range(N-x+1, N+1):
        numerator = numerator * i % mod
    denominator = 1
    for j in range(1, x+1):
        denominator = denominator * j % mod
    d = pow(denominator, mod-2, mod)
    return numerator * d
 
a = comb(n, a)
b = comb(n, b)
 
print((pow(2, n, mod) -1 -a -b) % mod)
A = list(map(int,input().split()))

count = N
Sum = 0

for l in range(0, N-2):
    Sum = A[l]
    for r in range(l+1, N-1):
        if Sum + A[r] != Sum ^ A[r]:
            break
        else:
            Sum += A[r]
            #count += 1
    count += r-l-1
print(count)

### FIXED CODE ###

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

count = 0
Sum = 0
r = 0

for l in range(0, N):
    #Sum = A[l]
    while r < N and Sum + A[r] == Sum ^ A[r]:
            Sum += A[r]
            r += 1
    count += r-l
    if(l==r):
        r+=1
    else:
        Sum -= A[l]
    
    
print(count)
N = input()
A = [x for x in input().split()]
five = False
three = False
for x in range(A):
  if(x%5==0):
    five = True
  elif(x%3==0):
    three = True
    
if(five.equals(True) and three.equals(True):
   print("APPROVED)
else:
   print("DENIED")
  


### FIXED CODE ###

N = input()
_list = input().split(" ")
_list = [int(x) for x in _list]
even = [x for x in _list if x % 2==0]
answer = []
for x in even:
    if x % 3 == 0 or x % 5 == 0:
        answer.append(True)
if len(even) == len(answer):
    print("APPROVED")
else:
    print("DENIED")
import numpy as np
L, R = map(int, input().split(" "))
arr = np.array(np.arange(L, R+1))
mod_list = []
min_mod_list = []
if (0 in (arr % 2019)) or (0 in arr):
  print(0)
else:
  for i in arr:
    
    for j in arr[arr != i]:
      mod_list.append(((i * j) % 2019))
    
    min_mod_list.append(min(mod_list))
    mod_list = []
  
  
  print(min(min_mod_list))

### FIXED CODE ###

import numpy as np

L, R = map(int, input().split(" "))
#L, R = 2020, 4000000000
if R - L > 2019:
    print(0)
else:
    arr = np.array(np.arange(L, R+1))
    mod_list = []
    min_mod_list = []
    
    if (0 in (arr % 2019)) or (0 in arr):
        print(0)
    else:
    
        for i in arr:
            mod_list = []
            index_ = np.where(arr==i)
            if i == arr[-1]:
                break
            
            for j in arr[int(index_[0])+1:]:
                mod_list.append((i * j) % 2019)
     
            min_mod_list.append(min(mod_list))
            if min(mod_list) == 0:
                break
    
    
        print(min(min_mod_list))
n=int(input())
a=0
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            a+=g[g[i][j]][k]
print(a)

### FIXED CODE ###

from math import *
g=[[0]*202 for _ in range(202)]
for i in range(1,201):
    for j in range(1,201):
        g[i][j]=gcd(i,j)
n=int(input())
a=0
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            a+=g[g[i][j]][k]
print(a)
A = int(input())
B = int(input())
if A > B:
    print(2 * A - 1)
elif A < B:
    print(2 * B - 1)
else:
    print(2 * A)

### FIXED CODE ###

A,B=(int(x) for x in input().split())
if A > B:
    print(2 * A - 1)
elif A < B:
    print(2 * B - 1)
else:
    print(2 * A)
N, T = map(int, input().split())
t = list(map(int, input().split()))

res = 0
for i in range(N - 1):
    res += min(T, t[i + 1] - t[i])

if t[-2] + T <= t[-1]:
    res += T 

print(res)


### FIXED CODE ###

N, T = map(int, input().split())
t = list(map(int, input().split()))

res = 0
for i in range(N - 1):
    res += min(T, t[i + 1] - t[i])

res += T

print(res)
N=input()
a=int(N)
b=list(N)
sum=0

for i in b:
  sum+=i
 
if a%sum==0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

N=input()
a=int(N)
b=list(N)
sum=0

for i in b:
  sum+=int(i)
 
if a%sum==0:
  print('Yes')
else:
  print('No')
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if fq[ps]:
                    nw = a[ps][ls[ps]]
                    if fq[nw]:
                        rw = a[nw][ls[nw]]
                        if ps == rw:
                            ql.append([d+1, ps])
                            ql.append([d+1, nw])
                            if ls[ps] < n + 1:
                                ls[ps] += 1
                            if ls[nw] < n + 1:
                                ls[nw] += 1
                            fq[nw] = False
                            fq[ps] = False
            else:
                ql.appendleft([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q + 1])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
            else:
                print(-1)
                exit()


if __name__ == '__main__':
    slove()
from collections import defaultdict
import math


def kari():
    map(int, input().split())
    list(map(int, input().split()))
    math.ceil()

def main():
    num = int(input())
    data = list(map(int, input().split()))
    data_kari = data.copy()
    data_kari.sort()
    # print(data_kari)
    min_chuou = data_kari[(num // 2) - 1]
    max_chuou = data_kari[num // 2]

    # print(min_chuou, max_chuou)

    # print(data)

    for i in range(num):
        if data[i] <= min_chuou:
            print(max_chuou)
        elif data[i] >= max_chuou:
            print(min_chuou)






if __name__ == '__main__':
    main()



### FIXED CODE ###


def main():
    num = int(input())
    data = list(map(int, input().split()))
    data_kari = data.copy()
    data_kari.sort()
    # print(data_kari)
    min_chuou = data_kari[(num // 2) - 1]
    max_chuou = data_kari[num // 2]

    # print(min_chuou, max_chuou)

    # print(data)

    for i in range(num):
        if data[i] <= min_chuou:
            print(max_chuou)
        elif data[i] >= max_chuou:
            print(min_chuou)






if __name__ == '__main__':
    main()
import sys
s = input()
k = input()

for i in range(len(s)):
    if s[i] != "1" and i + 1 < k:
        print(s[i])
        sys.exit(0)
print(1)


### FIXED CODE ###

s = input()
k = int(input())
tmp = 1
for i in range(len(s)):
    if s[i] != '1' and i + 1 <= k:
        tmp = int(s[i])
        break
print(tmp)
a = int(input())
b = int(input())
def aez(n, k):
    s = str(n)
    ln = len(s)-1
    n1 = int(s[0])
    if k == 1:
        return 9 * ln + n1 
    elif k == 2:
        return (81 * ln * (ln-1) // 2) + aez(int('9'*ln), 1)*(n1-1) + aez(int(s[1:]), 1)
    else:
        return (729*ln*(ln-1)*(ln-2)//6) + aez(int('9'*ln), 2)*(n1-1) + aez(int(s[1:]), 2)
print(aez(a, b))

### FIXED CODE ###

a = int(input())
b = int(input())
def aez(n, k):
    s = str(n)
    ln = len(s)-1
    n1 = int(s[0])
    if len(s) < k:
        return 0
    else:
        if k == 1:
            return 9 * ln + n1 
        elif k == 2:
            return (81 * ln * (ln-1) // 2) + aez(int('9'*ln), 1)*(n1-1) + aez(int(s[1:]), 1)
        else:
            return (729*ln*(ln-1)*(ln-2)//6) + aez(int('9'*ln), 2)*(n1-1) + aez(int(s[1:]), 2)
print(aez(a, b))
s=int(input())
mod=10**9+7
dp=[0]*(s+1)
dp[1]=0
dp[2]=0

for i in range(3,s+1):
    for j in range(3,i+1):
        dp[i]+=(dp[i-j])%mod
    dp[i]+=1

print(dp[s]%mod)


### FIXED CODE ###

s=int(input())
ans=0
mod=10**9+7
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

for i in range(1,s//3+1):
    ans+=(combinations_count(s-3*i+i-1,s-3*i))%mod
print(ans%mod)
a, b=int(map(input()))
print(a*b, a*2+b*2)

### FIXED CODE ###

a, b=map(int,input().split())
print(a*b, a*2+b*2)
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1


class Node:
    def __init__(self, parent, left):
        """
        Left-child, Right-sibiling
        """
        self.parent = parent
        self.left = left
        self.right = []
        self.point = 0

    def __str__(self):
        return f'parent = {self.parent}, left = {self.left}, right = {self.right}, point = {self.point}'


def set_point(T, node, point):
    T[node].point += point

    if T[node].left != NIL:
        l_child = T[node].left
        set_point(T, l_child, point)
        # T[l_child].point += point

    if T[node].right:
        for idx in range(len(T[node].right)):
            r_child = T[node].right[idx]
            set_point(T, r_child,  point)
            # T[r_child].point += point


N, Q = map(int, input().split())
T = {k: Node(NIL, NIL) for k in range(N)}

for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if T[a].left == NIL:
        left_child = b
        T[a].left = left_child
        T[left_child].parent = a
    else:
        T[a].right.append(b)
        T[b].parent = a

# for i in range(N):
#     print(i, T[i])

for j in range(Q):
    p, x = map(int, input().split())
    p -= 1
    set_point(T, p, x)


scores = []
for i in range(N):
    scores.append(T[i].point)

print(*scores)

# def main():


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


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1


N, Q = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(N - 1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N + 1)
for p, x in PX:
    value[p] += x

q = [(1, 0)]
while q:
    x, parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y, x))

ans = ' '.join(map(str, value[1:]))
print(ans)
a = list(map(int, input().split()))
O = input()

class Dice():
 def __init__(self, d):
  self.dice = d
 def S(self):
  one = self.dice[4]
  two = self.dice[0]
  five = self.dice[5]
  six = self.dice[1]
  InsSN(one, two, five, six)

 def InsSN(self, one, two, five, six):
  self.dice[0] = one
  self.dice[1] = two
  self.dice[4] = five
  self.dice[5] = six

 def N(self):
  one = self.dice[1]
  two = self.dice[5]
  five = self.dice[0]
  six = self.dice[4]
  InsSN(one, two, five, six)
  
 def InsWE(self, one, three, four, six):
  self.dice[0] = one
  self.dice[2] = three
  self.dice[4] = four
  self.dice[5] = six
 
 def W(self):
  one = self.dice[2]
  three = self.dice[5]
  four = self.dice[0]
  six = self.dice[3]
  InsWE(one, three, four, six)

 def E(self):
  one = self.dice[3]
  three = self.dice[0]
  four = self.dice[5]
  six = self.dice[2]
  InsWE(one, three, four, six)

di = Dice(a)

for i in range(len(O)):
 if O[i] == 'S':
  di.S()
 elif O[i] == 'N':
  di.N()
 elif O[i] == 'E':
  di.E()
 elif O[i] == 'W':
  di.W()

print(di.dice[0])





 













  

### FIXED CODE ###

d = list(map(int, input().split()))
order = input()
class Dice():
    def __init__(self, d):
        self.dice = d

    def InsSN(self, one, two, five, six):
        self.dice[0] = one
        self.dice[1] = two
        self.dice[4] = five
        self.dice[5] = six
        
    def InsWE(self, one, three, four, six):
        self.dice[0] = one
        self.dice[2] = three
        self.dice[3] = four
        self.dice[5] = six

    def S(self):
        one = self.dice[4]
        two = self.dice[0]
        five = self.dice[5]
        six = self.dice[1]
        self.InsSN(one, two, five, six)

    def N(self):
        one = self.dice[1]
        two = self.dice[5]
        five = self.dice[0]
        six = self.dice[4]
        self.InsSN(one, two, five, six)
 
    def W(self):
        one = self.dice[2]
        three = self.dice[5]
        four = self.dice[0]
        six = self.dice[3]
        self.InsWE(one, three, four, six)
        
    def E(self):
        one = self.dice[3]
        three = self.dice[0]
        four = self.dice[5]
        six = self.dice[2]
        self.InsWE(one, three, four, six)
        
    def roll(self, order):
        if order == 'S':
            self.S()
        elif order == 'N':
            self.N()
        elif order == 'E':
            self.E()
        elif order == 'W':
            self.W()
d = Dice(d)
for o in order:
    d.roll(o)
print(d.dice[0])
c=input()
if(c.isupper()==True):
  	print('A')
else
	print('a')
  

### FIXED CODE ###

c=input()
if(c.isupper()==True):
  print('A')
else:
  print('a')
s = map(input().split())
ans=0

for i in range(3):
  n = i*s
  if n in s:
    print(i)

### FIXED CODE ###

s = input()
ans = 0

for i in range(1,4):
  p = "R"*i
  if p in s:
    ans = i
    
print(ans)
import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class edge:
    def __init__(self, to, id): self.to, self.id = to, id

def main():
    N = Z()
    col = [0] * (N-1)
    G = collections.defaultdict(list)
    for i in range(N-1):
        a, b = ZZ()
        G[a].append(edge(b, i))
        G[b].append(edge(a, i))
    numCol = 0
    for i in range(1, N+1): numCol = max(numCol, len(G[i]))

    def dfs(v):
        colSet = set()
        for ed in G[v]:
            if col[ed.id] != 0: colSet.add(col[ed.id])
        c = 1
        for ed in G[v]:
            if col[ed.id] != 0: continue
            while c in colSet: c += 1
            col[ed.id] = c
            c += 1
            dfs(ed.to)

    dfs(1)
    print(numCol)
    for i in range(N-1): print(col[i])

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections
import sys
sys.setrecursionlimit(10 ** 8)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class edge:
    def __init__(self, to, id): self.to, self.id = to, id

def main():
    N = Z()
    col = [0] * (N-1)
    G = collections.defaultdict(list)
    for i in range(N-1):
        a, b = ZZ()
        G[a].append(edge(b, i))
        G[b].append(edge(a, i))
    numCol = 0
    for i in range(1, N+1): numCol = max(numCol, len(G[i]))

    def dfs(v):
        colSet = set()
        for ed in G[v]:
            if col[ed.id] != 0: colSet.add(col[ed.id])
        c = 1
        for ed in G[v]:
            if col[ed.id] != 0: continue
            while c in colSet: c += 1
            col[ed.id] = c
            c += 1
            dfs(ed.to)

    dfs(1)
    print(numCol)
    for i in range(N-1): print(col[i])

    return

if __name__ == '__main__':
    main()
n = int(input())
m = list(map(int, input().split()))

l = {}
ll = {}

if n % 2 == 0:
  for i in m:
    l[2*(i//2)+1] = 2
    if i in ll:
      ll[i] += 1
    else:
      ll[i] = 1
else:
  for i in m:
    if 2*(i//2) == 0:
      l[2*(i//2)] = 1
    else:
      l[2*(i//2)] = 2
    if i in ll:
      ll[i] += 1
    else:
      ll[i] = 1

if l != ll:
  print(0)
  exit()

print(1 << (n // 2) / (10**9+7))


### FIXED CODE ###

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

l = {}
ll = {}

if n % 2 == 0:
  for i in m:
    l[2*(i//2)+1] = 2
    if i in ll:
      ll[i] += 1
    else:
      ll[i] = 1
else:
  for i in m:
    if 2*(i//2) == 0:
      l[2*(i//2)] = 1
    else:
      l[2*(i//2)] = 2
    if i in ll:
      ll[i] += 1
    else:
      ll[i] = 1

if l != ll:
  print(0)
  exit()

print((1 << (n // 2)) % ((10 ** 9) + 7))