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

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7

        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(set)
        g = sys.stdin.readlines()
        for i in range(n - 1):
            a, b = [int(_) for _ in g[i].strip().split()]
            a -= 1
            b -= 1
            adj[a].add(b)
            adj[b].add(a)


        dp = [-1] * n
        done = [0] * n

        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    dp[s] = 0
                    return 0
                res *= rem * dfs(x, k - 2)
                res %= MOD
                rem -= 1
                if res == 0:
                    dp[s] = 0
                    return 0

            dp[s] = res
            return res

        dfs(0, k - 1)

        print((dp[0] * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7
        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].append(b)
            adj[b].append(a)
        done = [0] * n
        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    return 0
                res = (res * rem) % MOD
                res = (res * dfs(x, k - 2)) % MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print((dfs(0, k - 1) * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()
### BUGGY CODE ###

n = int(input())

a = [0] * n
for i in range(n):
    a[i] = int(input())

loop = [0] * n


if (2 not in a):
    print(-1)
    exit()

tar_index = 0
loop[0] = 1
# 何回目で２に到達するか
count = 0

while True:
    tar_index = a[tar_index] - 1
    #print(count, tar_index)
    count += 1

    if (tar_index == 1):
        print(count)
        exit()

    # 一回行った場所に戻ると、循環してるのでOUT
    if (loop[tar_index] == 1):
        print(-1)
        exit()


### FIXED CODE ###

n = int(input())

a = [0] * n
for i in range(n):
    a[i] = int(input())

loop = [0] * n


if (2 not in a):
    print(-1)
    exit()

tar_index = 0
loop[0] = 1
# 何回目で２に到達するか
count = 0

while True:
    tar_index = a[tar_index] - 1
    #print(count, tar_index)
    count += 1

    if (tar_index == 1):
        print(count)
        exit()

    # 一回行った場所に戻ると、循環してるのでOUT
    if (loop[tar_index] == 1):
        print(-1)
        exit()

    loop[tar_index] = 1
### BUGGY CODE ###

import numpy as np
from itertools import product

D = int(input())
C = np.array(list(map(int, input().split())))
S = np.array([list(map(int, input().split())) for d in range(D)])

L = np.empty(26, int)
L[:] = -1

P2 = list(product(range(26), repeat=2))
P3 = list(product(range(26), repeat=3))

for d in range(0, 363, 3):
    scores = []
    for t in P3:
        LL = L.copy()

        score = 0
        for tt, dd in zip(t, range(d, d+3)):
            LL[tt] = dd
            score += S[d, tt] - np.dot(C, dd-LL)

        scores.append(score)

    smax = scores[0]
    tmax = 0
    for t, s in enumerate(scores):
        if s>smax:
            smax = s
            tmax = t

    for tt, dd in zip(P3[tmax], range(d, d+3)):
        L[tt] = dd
        print(tt+1)

d = 363
scores = []
for t in P2:
    LL = L.copy()

    score = 0
    for tt, dd in zip(t, range(d, d+2)):
        LL[tt] = dd
        score += S[d, tt] - np.dot(C, dd-LL)

    scores.append(score)

smax = scores[0]
tmax = 0
for t, s in enumerate(scores):
    if s>smax:
        smax = s
        tmax = t

for tt, dd in zip(P2[tmax], range(d, d+3)):
    L[tt] = dd
    print(tt+1)


### FIXED CODE ###

import numpy as np

D = int(input())
C = list(map(int, input().split()))
for d in range(D):
    S = np.array(list(map(int, input().split())))
    print(np.argmax(S)+1)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
if n == 1:
	print(a_list[0])
	exit()
isEven = n%2 == 0
b_list = [a_list[1], a_list[0]] if isEven else [a_list[0]] 
index = 2 if isEven else 1
for i in range(index, n, 2):
	b_list.insert(0, a_list[i+1])
	b_list.append(a_list[i])	
r = ' '.join(list(map(str, b_list)))
print(r)

### FIXED CODE ###

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

    if n == 1:
        print(data[0])
    else:
        result = [None] * n

        if n % 2 == 0:
            center = int(n / 2)
            for index, value in enumerate(data):
                if index % 2 == 0:
                    result[center + int(index / 2)] = value
                else:
                    result[center - int((index + 1) / 2)] = value
            print(" ".join(str(n) for n in result))
        else:
            center = int(n / 2)
            for index, value in enumerate(data):
                if index % 2 == 0:
                    result[center - int(index / 2)] = value
                else:
                    result[center + int((index + 1) / 2)] = value
            print(" ".join(str(n) for n in result))

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

MOD = 10**9 + 7


def main():
    L = input()
    N = len(L)
    dp = [[0]*2 for i in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        # smaller: 1 -> 1
        if L[i] == "1":
            dp[i+1][1] += dp[i][1] * 3
        else:
            dp[i+1][1] += dp[i][1] * 3
        # smaller: 0 -> 1
        if L[i] == "1":
            dp[i+1][1] += dp[i][0] * 1
        # smaller: 0 -> 0
        if L[i] == "1":
            dp[i+1][0] += dp[i][0] * 2
        else:
            dp[i+1][0] += dp[i][0] * 1
    print((dp[N][0]+dp[N][1]) % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    # 写経AC
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0]*2 for i in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        # a+b = 0
        if S[i] == '0':
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]
        else:
            dp[i+1][1] = dp[i][0] + dp[i][1]
            dp[i+1][1] %= MOD
        # a+b = 1
        if S[i] == '0':
            dp[i+1][1] += dp[i][1]*2
            dp[i+1][1] %= MOD
        else:
            dp[i+1][0] += dp[i][0]*2
            dp[i+1][0] %= MOD
            dp[i+1][1] += dp[i][1]*2
            dp[i+1][1] %= MOD
    print((dp[N][0]+dp[N][1]) % MOD)


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

import sys
sys.setrecursionlimit(10**6)
import time
start = time.time()
n = int(input())
al = list(map(int,input().split()))

#a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

#a,bの最小公倍数
def lcm(a, b):
   return a * b // gcd (a, b)


tmp = 1
for a in al:
    tmp = lcm(tmp, a)
    if time.time() - start > 1.9:
        print(sum(al))
        import sys
        sys.exit()

ans = 0
for a in al:
    ans += tmp // a
    ans %= 10**9 + 7
    if time.time() - start > 1.9:
        print(sum(al))
        import sys
        sys.exit()
print(ans)

### FIXED CODE ###

import fractions
n = int(input())
al = list(map(int,input().split()))
al = sorted(al)
p = al[0]
for i in range(1, n):
    p = p * al[i] // fractions.gcd(p, al[i])

ans = 0

for a in al:
    ans += p // a

print(ans % (10**9 + 7))
### BUGGY CODE ###

#!/usr/bin/env python

n, k = map(int, input().split())
L = [0 for _ in range(k)]
R = [0 for _ in range(k)]
for i in range(k):
    L[i], R[i] = map(int, input().split())
mod = 998244353

dp = [0 for _ in range(n+1)]
dp[0] = 0 
dp[1] = 1 

def cont(x, y): 
    ret = []
    for i in range(x, y+1):
        ret.append(i)
    return ret 

s = []
for i in range(k):
    s += cont(L[i], R[i])

for i in range(2, n+1):
    for j in range(len(s)):
        if i-s[j] > 0:
            dp[i] += (dp[i-s[j]])%mod

print(dp[n]%mod)


### FIXED CODE ###

#!/usr/bin/env python

n, k = map(int, input().split())
L = [0 for _ in range(k)]
R = [0 for _ in range(k)]
for i in range(k):
    L[i], R[i] = map(int, input().split())
mod = 998244353

dp = [0 for _ in range(n+1)]
dp[1] = 1 
cumsum = [0 for _ in range(n+1)]
cumsum[1] = 1 

# O(NK)
for i in range(2, n+1):
    for j in range(k):
        li = i-R[j]
        ri = i-L[j]
        if ri<0: continue
        li = max(li, 1)
        dp[i] += (cumsum[ri]-cumsum[li-1])%mod
    cumsum[i] = cumsum[i-1]+dp[i]

print(dp[n]%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2*(10**5)+1)
N, Q = map(int,input().split())
T = [[] for k in range(N)]
V = [0]*N
for _ in range(N-1):
    a, b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
for q in range(Q):
    p, x = map(int,input().split())
    V[p-1] += x

def dfs(mae,ima):
    for tsugi in T[ima]:
        if tsugi != mae:
            V[tsugi] += V[ima]
            dfs(ima,tsugi)
dfs(-1,0)
print(*V)


### FIXED CODE ###

import sys
sys.setrecursionlimit(200010)

def main():
    input = sys.stdin.readline
    N, Q = map(int,input().split())
    G = [[] for k in range(N+1)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a].append(b)
    kyori = [0 for k in range(N+1)]
    for k in range(Q):
        p, x = map(int,input().split())
        kyori[p] -= x
    def dfs(now, dist):
        for tsugi in G[now]:
            if kyori[tsugi] <= 0:
                kyori[tsugi] = -kyori[tsugi]
                kyori[tsugi] += dist
                dfs(tsugi, kyori[tsugi])
    kyori[1] = -kyori[1]
    dfs(1,kyori[1])
    print(*kyori[1:], sep = " ")

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

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

threshold = 1000000007

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += (list_A[i] * list_A[j] % threshold)
ans = ans % threshold
print(ans)

### FIXED CODE ###

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

threshold = 1000000007
tmp = sum(list_A[1:])
ans = 0
for i in range(N-1):
    if i == 0:
        ans += list_A[i] * tmp % threshold
    else:
        tmp = tmp - list_A[i]
        ans += (list_A[i] * tmp % threshold)
ans = ans % threshold
print(ans)
### BUGGY CODE ###

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

k += 1

ans = 0
for x in range(k):
    for y in range(k):
        for z in range(k):
            if x + y + z == s:
                ans += 1

print(ans)


### FIXED CODE ###

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

k += 1

ans = 0
for x in range(k):
    for y in range(k):
        if s - (x + y) >= 0 and s - (x + y) <=k-1:
                ans += 1

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

from sys import stdin
from sys import setrecursionlimit
from collections import Counter

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
a.sort()
c = Counter(a)

se = set()

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

for i in a:
    k = make_divisors(i)
    flag = True
    for j in k:
        if j in se:
            flag = False
    if flag:
        se.add(i)

point = len(se)

for i in se:
    if c[i] > 1:
        point -= 1

print(point)

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit
from collections import Counter
from numba import jit

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
a.sort()
b = list(set(a))
b.sort()
c = Counter(a)

se = set()

@jit
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

for i in b:
    k = make_divisors(i)
    flag = True
    for j in k:
        if j in se:
            flag = False
            break
    if flag:
        se.add(i)

point = len(se)

for i in se:
    if c[i] > 1:
        point -= 1

print(point)
### BUGGY CODE ###

import fractions
import sys

sys.setrecursionlimit(1000000)

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

g_list = []

if len(l) == 2:
  g_list.append(max(l[0],l[1]))
  
else:
    g = fractions.gcd(l[1],l[2])
    for j in range(3,N):
        g = fractions.gcd(g,l[j])
    g_list.append(g)

    g = fractions.gcd(l[0],l[2])
    for j in range(3,N):
        g = fractions.gcd(g,l[j])
    g_list.append(g)

    for i in range(N):
        g = fractions.gcd(l[0],l[1])
        for j in range(N):
            if j != i:
                g = fractions.gcd(g,l[j])
        g_list.append(g)

print(max(g_list))




### FIXED CODE ###

import fractions

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

L = [0]
R = [0]

gl = 0
gr = 0
for i in range(N):
    gl = fractions.gcd(gl,l[i])
    L.append(gl)
    gr = fractions.gcd(gr,l[N-1-i])
    R.append(gr)

M = []
for i in range(N+1):
    M.append(fractions.gcd(L[i-1],R[N-i]))

print(max(M))
### BUGGY CODE ###

from collections import deque


def bfs(x, y):
    path = [float('inf')] * N
    q = deque()
    q.append(x)
    path[x] = 0
    while q:
        p = q.popleft()
        for np, d in edge[p]:
            if path[np] > path[p] + d:
                path[np] = path[p] + d
                q.append(np)
    
    return path[y]


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
q = []
for i in range(N):
    for j in range(i + 1, N):
        q.append((A[i][j], i, j))

q.sort()

# B = [[float('inf')] * N for _ in range(N)]

ans = 0
edge = [[] for _ in range(N)]
for a, i, j in q:
    b = bfs(i, j)
    if a < b:
        edge[i].append((j, a))
        edge[j].append((i, a))
        ans += a
    elif a == b:
        pass
    else:
        print(-1)
        exit()

print(ans)


### FIXED CODE ###

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

dp = A
cnt = 0
for i in range(N):
    for j in range(N):
        if all(dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j):
            cnt += dp[i][j]
        if any(dp[i][j] > dp[i][k] + dp[k][j] for k in range(N)):
            print(-1)
            exit()

print(cnt // 2)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
            else:
                ans += bit_acc[j] * (2 ** (leng - j - 1))
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()   




### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from math import gcd
k = int(input())
sum = 0
for a in range(k):
    for b in range(k):
        for c in range(k):
            sum += gcd(gcd(a + 1, b + 1), c + 1)
print(sum)

### FIXED CODE ###

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

k = int(input())
sum = 0

for i in range(1, k + 1):
    for j in range(1, k + 1):
        gcd_ij = gcd(i, j)
        for k in range(1, k + 1):
            sum += gcd(gcd_ij, k)
print(sum)
### BUGGY CODE ###

H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()] for i in range(H)]
def r(X):
    Y = [[0 for x in range(len(X))] for xx in range(len(X[0]))]
    for i in range(len(X[0])):
        for j in range(len(X)):
            # print(i,j)
            Y[i][j] = X[len(X)-j-1][i]
    return Y
    
    
c = 0
for t in range(4):
    X = r(X)
    for i in range(len(X)):
        for j in range(len(X[0])):
            if X[i][j] > 0:
                for n in range(1, min(i+1, len(X[0])-j)):
                    if i-n >= 0 and i-n < len(X) and j+n >= 0 and j+n < len(X[0]):
                        if X[i-n][j+n] > 0:
                            for m in range(n):
                                if i-n-m >= 0 and i-n-m < len(X) and j-n+m >= 0 and j-n+m < len(X[0]):
                                    if X[i-n-m][j-n+m] > 0:
                                        #print (i,j,n,m, "get1")
                                        c += 1
print (c)


### FIXED CODE ###

H, W = map(int, input().split())
I = [input() for _ in range(H)]
X = [[[0, 1][a=="#"] for a in inp] for inp in I]
k = 32
def r():
    global H, W, I
    I = ["".join([I[H - 1 - j][i] for j in range(H)]) for i in range(W)]
    H, W = W, H
def st1(s):
    return int(s.replace("#", "1" * k).replace(".", "0" * k), 2)
def st2(s):
    return int(s.replace("#", "0" * (k - 1) + "1").replace(".", "0" * k), 2)
def getsum(x):
    for i in range(8):
        x += x >> (k << i)
    return x & ((1 << k) - 1)

ans = 0
for _ in range(4):
    A1 = [st1(inp) for inp in I]
    A2 = [st1("".join([I[i][j] for i in range(H)])) for j in range(W)]
    B = [st2(inp[::-1]) for i, inp in enumerate(I)]
    C = [[0] * W for _ in range(H)]
    for j in range(W):
        s = 0
        m = (1 << j * k) - 1
        for i in range(H)[::-1]:
            s <<= k
            s += B[i] >> (j+1) * k
            s &= m
            C[i][j] = s
    for i in range(1, H):
        for j in range(1, W):
            ans += A1[i] >> (W - j) * k & A2[j] >> (H - i) * k & C[i][j]
    r()
            
print(getsum(ans))
### BUGGY CODE ###

N, K = list(map(int, input().split()))
candles = list(map(int, input().split()))
abs_c = [abs(c) for c in candles]
result = []
for n in range(N-K+1):
    route = candles[n:n+K]
    r1 = abs(route[0]) + abs(route[-1]-route[0])
    r2 = abs(route[-1]) + abs(route[0]-route[-1])
    result.append(min(r1, r2))

print(min(result))

### FIXED CODE ###

N, K = list(map(int, input().split()))
candles = list(map(int, input().split()))
abs_c = [abs(c) for c in candles]
result = []
for n in range(N-K+1):
    r1 = abs(candles[n]) + abs(candles[n+K-1]-candles[n])
    r2 = abs(candles[n+K-1]) + abs(candles[n]-candles[n+K-1])
    result.append(min(r1, r2))

print(min(result))
### BUGGY CODE ###

k=int(input())
if k&1==0:
  print(-1)
  exit()
elif 7%k==0:
  print(1)
  exit()
m=7
a=b=1
while(m>0):
  a=a*10%k
  m=(m+7*a)%k
  b+=1
print(b)

### FIXED CODE ###

k=int(input())
if k&1==0 or k%5==0:
  print(-1)
  exit()
elif 7%k==0:
  print(1)
  exit()
m=7
a=b=1
while(m>0):
  a=a*10%k
  m=(m+7*a)%k
  b+=1
print(b)
### BUGGY CODE ###

n,c,k = map(int,input().split())
#cは乗客kは時間
T = []
for i in range(n):
    t = int(input())
    T.append(t)
T.sort()
bus = 0
while(True):
    if len(T) == 0:
        break
    start = T[0]
    for i in range(c):
        if len(T)!=0: 
            if start+k >= T[0]:
                T.remove(T[0])
    bus += 1
print(bus)

### FIXED CODE ###

n,c,k = map(int,input().split())
#cは乗客kは時間
T = []
for i in range(n):
    t = int(input())
    T.append(t)
T.sort()
bus = 0
while(True):
    if len(T) == 0:
        break
    start = T[0]
    for i in range(c):
        if len(T)!=0: 
            if start+k >= T[0]:
                T.remove(T[0])
            else:
                break
    bus += 1
print(bus)
### BUGGY CODE ###

def gcdf(a,n,gcdv):
#    print("a:",a)
    a0=a[0]
    ramin=10**9
    ramin0=20**9
    while ramin0!=ramin:
        ramin0=ramin
        for i in range(n):
            a[i]=a[i]%a0
            if a[i]==0:
                a[i]=a0
            if ramin>a[i]:
                ramin=a[i]
            if ramin<=gcdv:
                return gcdv
        a0=min(a)
#        print("a:",a,ramin)
    return ramin


#n=2
#a=[1000000000, 1000000000]
#n=4
#a=[15, 18, 24, 36]
n=int(input())

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

#print(a)
if n==2:
    print(max(a))
else:
    gcdv=0
    a.sort(reverse=True)
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy,n-1,gcdv)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)


### FIXED CODE ###

def gcdf(a):
    a.sort()
#    print("a2:",a)
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
#    print("a2:",a)
    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 

#n=8
#a=[746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#ans=[19]
#n=2
#a=[1000000000, 1000000000]
#n=5
#a=[15, 18, 24, 36, 81]
#n=3
#a=[7, 6, 8]
n=int(input())
a=[]
for i in map(int,input().split()):
    a.append(i)
if n==2:
    print(max(a))
elif n<2**10:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=int(n**(1/2))
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)
    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        gcdrg1=gcdf(rgcd1)
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
#        print(mi,gcdf(am),len(am),gcdf(rgcd1))
        for i in range(len(am)):
            acpy=list(am)
#            del acpy[i]
#            acpy.append(gcdrg1)
            acpy[i]=gcdrg1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx
    print(gcdv)
### BUGGY CODE ###

# coding: utf-8


def main():
    # n = map(int, input().split(" "))
    n = int(input())
    m = []
    count = 0
    for _ in range(n):
        m.append(input())
    for i in range(n):
        for j in range(i+1, n):
            if is_anagram(m[i], m[j]):
                count += 1
    print(count)


def is_anagram(s1, s2):
    s1_length = len(s1)
    s2_length = len(s2)
    if s1_length != s2_length:
        return False
    else:
        for index in range(s1_length):
            search_char = s1[index: index+1]
            search_result = s2.find(search_char)
            if search_result == -1:
                return False
            else:
                s2 = s2.replace(search_char, "", 1)
    return True

main()

### FIXED CODE ###

# coding: utf-8
import math

anagramed = []

def main():
    # n = map(int, input().split(" "))
    n = int(input())
    m = []
    r = {}
    count = 0

    for _ in range(n):
        m.append(input())
        anagramed.append(False)

    for i in range(n):
        s = "".join(sorted(m[i]))
        if r.get(s) is None :
            r[s] = 1
        else:
            count += r[s]
            r[s] += 1
    print(count)


main()