Harryxun/stf_run huggingface dataset:
#第一回日本最強プログラマー学生選手権-予選- -B Kleene Inversion
"""
リストをk回繰り返したものの、転倒数の個数を求めよ
先ず純粋に与えられたリスト内での転倒数を求めた後、
それを1~k倍したものを足し合わせる
"""
import sys
sys.setrecursionlimit(1000000)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

class BinaryIndexedTree():
    def __init__(self, seq):
        self.size = len(seq)
        self.depth = self.size.bit_length()
        self.build(seq)
        
    def build(self,seq):
        data = seq
        size = self.size
        for i,x in enumerate(data):
            j = i+(i&(-i))
            if j < size:
                data[j] += data[i]
        self.data = data
        
    def __repr__(self):
        return self.data.__repr__()
        
    def get_sum(self,i):
        data = self.data
        s = 0
        while i:
            s += data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        data = self.data
        size = self.size
        while i < size:
            data[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        data = self.data; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + data[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
#バブルソート(隣り合う2数を入れ替えて順列を昇順にする時の最小手数) 
def Inversion(seq):
    # seqは、1,2,...,Nの順列
    N = len(seq)
    bit = BinaryIndexedTree([0] * (N+1))
    inv = N*(N-1)//2
    for x in seq:
        inv -= bit.get_sum(x)
        bit.add(x,1)
    return inv

res = Inversion(lst1)
#lst全体で見た時にそれより小さい値がいくつあるか
res2 = Inversion(sorted(lst1,reverse=True))
def reydeoro(n):
    return n*(n+1)//2
print((res*k+res2*reydeoro(k-1))%mod)

### FIXED CODE ###

#第一回日本最強プログラマー学生選手権-予選- -B Kleene Inversion
"""
リストをk回繰り返したものの、転倒数の個数を求めよ
先ず純粋に与えられたリスト内での転倒数を求めた後、
それを1~k倍したものを足し合わせる
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))
fall = 0
fall_al = 0
for i in range(n-1):
    for j in range(i+1,n):
        if lst1[i] > lst1[j]:
            fall += 1
lst1.sort(reverse=True)
for i in range(n-1):
    for j in range(i+1,n):
        if lst1[i] > lst1[j]:
            fall_al += 1

def reydeoro(n):
    return n*(n+1)//2
print((fall*k+fall_al*reydeoro(k-1))%mod)
def prepare(n):

    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def f(i, facts, invs):
    a = n - k - i + 1
    if a < 0:
        return 0
    b = k - i
    ans = facts[i + a] * invs[i] * invs[a] % MOD
    ans *= facts[i + b - 1] * invs[i - 1] * invs[b] % MOD
    return ans


n, k = list(map(int, input().split()))
facts, invs = prepare(n)

ans = []
for i in range(1, k + 1):
    ans.append(f(i, facts, invs))

print(*ans, sep="\n")

### FIXED CODE ###

def factorial_mod(n, mod):
    a = 1
    for i in range(1, n + 1):
        a *= i
        a %= mod
    return a


def cmb(n, k, mod):
    if k > n or k < 0:
        return 0
    fact_n = factorial_mod(n, mod)
    fact_k = factorial_mod(k, mod)
    fact_n_k = factorial_mod(n - k, mod)
    return (fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod)) % mod


n, k = map(int, input().split())
MOD = 10**9 + 7

for i in range(k):
    print(int(cmb(n - k + 1, i + 1, MOD) * cmb(k - 1, i, MOD) % MOD))
W,H=map(int,raw_input().split())
p=[input() for i in range(W)]
q=[input() for i in range(H)]

p.sort(reverse=True)
q.sort(reverse=True)

cost=0
del_H=0
del_W=0
len_p=W
len_q=H

while len_p>0 and len_q>0:
    
    if p[0]>q[0]:
        del_W+=1
        cost+=p[0]*(del_H+1)
        del p[0]
        len_p-=1
    else:
        del_H+=1
        cost+=q[0]*(del_W+1)
        del q[0]
        len_q-=1
        

if len_p==0:
    cost+=sum(q)*(W+1)

else:
    cost+=sum(p)*(H+1)

print cost


### FIXED CODE ###

s=raw_input()
true_s='CODEFESTIVAL2016'

error_number=0

for i in range(16):
    if s[i]!=true_s[i]:
        error_number+=1


print error_number
import numpy as np
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
table = np.zeros((H , W))
done = np.zeros((H , W))
max = 0
print(s[0][1])

for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            continue
        if done[i][j] == 1:
            continue
        l = 0
        while j + l < W:
            if s[i][j + l] == "#":
                break
            l += 1
        for k in range(l):
            table[i][j + k] += l
            done[i][j+k] = 1
print(table)
done = np.zeros((H , W))
for j in range(W):
    for i in range(H):
        if s[i][j] == "#":
            continue
        if done[i][j] == 1:
            continue
        l = 0
        while i + l < H:
            if s[i + l][j] == "#":
                break
            l += 1
        for k in range(l):
            table[i + k][j] += l
            done[i + k][j] = 1
            if table[i + k][j] > max:
                max = table[i + k][j]

print(table)
print(int(max - 1))

### FIXED CODE ###

import numpy as np
H, W = map(int, input().split())
s = np.array([list(input()) for _ in range(H)])=="."

R = np.zeros((H,W),dtype = int)
L = np.zeros((H,W),dtype = int)
U = np.zeros((H,W),dtype = int)
D = np.zeros((H,W),dtype = int)

for i in range(H):
    U[i] = (U[i - 1] + 1) *s[i]
    D[- i - 1] = (D[-i] + 1) * s[-i-1]
for i in range(W):
    L[:,i] = (L[:,i-1] + 1) * s[:,i]
    R[:,-1-i] = (R[:,-i] + 1) * s[:,-i-1]
print(np.max(L+R+U+D - 3))
a = str(raw_input())
if 1a[0:4] == 'YAKI':
    print 'Yes'
else:
    print 'No'


### FIXED CODE ###

a = str(raw_input())
if a[0:4] == 'YAKI':
    print 'Yes'
else:
    print 'No'
import numpy as np 

np.arange(1, 100, N)



### FIXED CODE ###

N = int(input())

print(int(N*(N+1)/2))
h,w=map(int,input().split())
p=[["."]*(w+2)]+[["."]+list(map(str,input()))+["."]for i in range(w)]+[["."]*(w+2)]
print(["No","Yes"][int(all([any([p[i+x[0]][I+x[1]]=="#"for x in [[0,1],[0,-1],[1,0],[-1,0]]])for I in range(1,w+1)for i in range(1,h+1)if p[i][I]=="#"]))])

### FIXED CODE ###

h,w=map(int,input().split())
p=[["."]*(w+2)]+[["."]+list(map(str,input()))+["."]for i in range(h)]+[["."]*(w+2)]
print(["No","Yes"][int(all([any([p[i+x[0]][I+x[1]]=="#"for x in [[0,1],[0,-1],[1,0],[-1,0]]])for I in range(1,w+1)for i in range(1,h+1)if p[i][I]=="#"]))])
H, W = map(int, input().split(" "))

s = [list(input()) for _ in range(0, H)]

d = {}
def walk(i, j, c):
	if i < 0 or i >= H or j < 0 or j >= W:
		return
	if s[i][j] != ".":
		return
	if (i, j) in d and c >= d[(i, j)]:
		return

	d[(i, j)] = c
	for z in range(i-1, i+2):
		walk(z, j, c+1)
	for z in range(j-1, j+2):
		walk(i, z, c+1)

walk(0, 0, 1)
print(-1)

### FIXED CODE ###

INF=10*10
H,W=map(int, input().split())
s=[list(input()) for _ in range(H)]
wall=sum(map(lambda x: x.count("#"), s))
d=[[INF for _ in range(W)] for _ in range(H)]
def bfs(h, w, c):
	if d[h][w] <= c:
		return
	d[h][w] = c
	for dh,dw in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
		if h+dh >= 0 and w+dw >= 0 and h+dh < H and w+dw < W and s[h+dh][w+dw] == ".":
			bfs(h+dh, w+dw, c+1)
bfs(0, 0, 1)
print(-1 if d[H-1][W-1] == INF else H*W - d[H-1][W-1] - wall)
a,b=int(input().split())
c=a+b
d=a-b
e=a*b
print(max(c,d,e))


### FIXED CODE ###

a,b=map(int,input().split())
print(max(a + b,a - b,a * b))
import sys

N = int(input())

argv = input().split()
intList = [int(num) for num in argv]
intList.sort()

i = 0
j = 0
idel = 0

while i < N:
  j = i + 1
  while j < N:
    if (intList[j] % intList[i]) == 0:
      if (intList[j] == intList[i]):
        idel = 1
      del intList[j]
      N = N - 1
    else:
      j += 1
  if idel == 1:
    idel = 0
    del intList[i]
  i += 1

print(len(intList))

### FIXED CODE ###

N = int(input())

intList = list(map(int, input().split()))
intList.sort()

cntList = [1] * (intList[-1] + 1)

i = 0
j = 1
ans = 0

while i < (N - 1):
  base = intList[i]
  j = 1
  num = base
  if cntList[num] == 1:
    while num <= intList[-1]:
      if cntList[num] == 1:
        cntList[num] = 0
      j += 1
      num = base * j
    if intList[i] != intList[i+1]:
      ans += 1
  i += 1

if cntList[intList[-1]] == 1:
  ans += 1
  
print(ans)
num = map(int, input().split())

if num % 4 == 0:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

a, b, c = input().split()
num = int(a+b+c)

if num % 4 == 0:
    print('YES')
else:
    print('NO')
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [-1] * n
        # rank
        #self.rank = [0] * n
        self.size = [1] * n

    def find(self, x):
        # 根の番号を返す(所属する集合を確認する)
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        self.par[y]=x
        self.size[x]+=self.size[y]

import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
uf=UnionFind(n)
out=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    out[a-1].append(b-1)
    out[b-1].append(a-1)

for i in range(k):
    c,d=map(int,input().split())
    if uf.check(c-1,d-1):
        out[c-1].append(d-1)
        out[d-1].append(c-1)

for i in range(n):
    ans=uf.size[uf.find(i)]-1-len(out[i])
    print(ans,end=' ')


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [-1] * n
        # rank
        self.size = [1] * n

    def find(self, x):
        # 根の番号を返す(所属する集合を確認する)
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        self.par[y]=x
        self.size[x]+=self.size[y]

import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
uf=UnionFind(n)
out=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    out[a-1].append(b-1)
    out[b-1].append(a-1)

for i in range(k):
    c,d=map(int,input().split())
    if uf.check(c-1,d-1):
        out[c-1].append(d-1)
        out[d-1].append(c-1)

for i in range(n):
    ans=uf.size[uf.find(i)]-1-len(out[i])
    print(ans,end=' ')
import sys

for line in sys.stdin.readlines():
  line = line.strip()
  line = map(int, line)
  if line[0] == 0 and line[1] == 0:
    break
  else:
    print " ".join(map(str, sorted(line)))

### FIXED CODE ###

import sys

for line in sys.stdin.readlines():
  line = line.strip()
  line = map(int, line.split())
  if line[0] == 0 and line[1] == 0:
    break
  else:
    print " ".join(map(str, sorted(line)))
n,a,b,c,d=map(int,input().split())
a-=1
b-=1
c-=1
d-=1

temp=str(input())
maxim=max(a,b)
minim=min(a,b)
if temp[maxim:].count("...")!=0 or temp[maxim+1]==temp[maxim+2]=="." or temp[maxim+1]==temp[maxim-1]==".":
    flag=1
else:
    flag=0
    
s=list(temp)
s[a]="A"
s[b]="B"
s[c]="C"
s[d]="D"

mac=max(c,d)
ans=1

for i in range(minim,mac):
    if s[i]==s[i+1]=="#":
        ans=0


elif c<d and ans==1:
    ans=1
elif c>d and ans==1:
    if flag==1:
        ans=1
    elif d<=len(s)-1:
        ans=1
    elif s[d-1]=="#" or s[d+1]=="#":
        ans=0
    else:
        ans=1
                
if ans==1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

temp=str(input())
maxim=max(a,b)
minim=min(a,b)
if temp[maxim:d+2].count("...")!=0 or temp[maxim+1]==temp[maxim+2]=="." or temp[maxim+1]==temp[maxim-1]==".":
    flag=1
else:
    flag=0
    
s=list(temp)
s[a]="A"
s[b]="B"
s[c]="C"
s[d]="D"

mac=max(c,d)
ans=1

for i in range(minim,mac):
    if s[i]==s[i+1]=="#":
        ans=0

if c<d and ans==1:
    ans=1
elif c>d and ans==1:
    if flag==1:
        ans=1
    elif s[d-1]=="#" or s[d+1]=="#":
        ans=0
    else:
        ans=1
                
if ans==1:
    print("Yes")
else:
    print("No")
import numpy as np
def gcd(a, b):
	if a > b:
		a, b = b, a
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
a = np.array([int(x) for x in input().split()])
np.sort(a)
l = np.zeros(n + 1)
r = np.zeros(n + 1)
m = np.zeros(n)
for i in range(n):
	l[i + 1] = gcd(l[i], a[i])
for i in reversed(range(n)):
	r[i] = gcd(r[i + 1], a[i])
for i in range(n):
	m[i] = gcd(l[i], r[i + 1])
print(int(np.max(m)))


### FIXED CODE ###

import numpy as np
def gcd(a, b):
	if a < b:
		a, b = b, a
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
a = np.array([int(x) for x in input().split()])
np.sort(a)
l = np.zeros(n + 1)
r = np.zeros(n + 1)
m = np.zeros(n)
for i in range(n):
	l[i + 1] = gcd(l[i], a[i])
for i in reversed(range(n)):
	r[i] = gcd(r[i + 1], a[i])
for i in range(n):
	m[i] = gcd(l[i], r[i + 1])
print(int(np.max(m)))
N,A = map(int,input().split())
X = sorted(map(int,input().split()))
Y = []
for x in X:
    Y.append(abs(A-x))
ans = Y[0]%Y[1]
for y in Y:
    for i in range(y-1,0,-1):
        if y%i == 0:
            ans = max(ans,i)
            break
print(ans)

### FIXED CODE ###

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

N,A = map(int,input().split())
X = sorted(map(int,input().split()))
Y = []
for x in X:
    Y.append(abs(A-x))
ans = max(Y)
for y in Y:
    ans = gcd(y,ans)
print(ans)
# ABC076C
S = input()
T = input()
check = -1
flag = True
for i in range(len(S)):
    flag = True
    if S[i] != T[0]:
        continue
    k = 1
    while k < len(T):
        if S[i+k] == "?":
            k += 1
        else:
            if S[i+k] == T[k]:
                k += 1
            else:
                flag = False
                break        
    if k == len(T) and flag == True:
        check = i

if check != -1:
    S = list(S)
    for i in range(len(T)):
        S[check + i] = T[i]
    S = "".join(S)
    ans = S.replace("?", "a")
    print(ans)
else:
    print("UNRESTORABLE")

### FIXED CODE ###

# ABC076C
S = input()
T = input()
check = -1
for i in range(len(S) - len(T) + 1):
    if S[i] == "?" or S[i] == T[0]:
        k = 1
        flag = True
        while k < len(T):
            if S[i+k] == "?":
                k += 1
            else:
                if S[i + k] == T[k]:
                    k += 1
                else:
                    flag = False
                    break
        if k == len(T) and flag == True:
            check = i

if check != -1:
    S = list(S)
    for i in range(len(T)):
        S[check + i] = T[i]
    S = "".join(S)
    ans = S.replace("?", "a")
    print(ans)
else:
    print("UNRESTORABLE")
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

N,Q = map(int,input().split())
AB = [[x for x in map(int,input().split())] for _ in range(N-1)]
PX = [[x for x in map(int,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)
 
cnt = [0]*N
for p,x in PX:
    cnt[p-1] += x
 
def dfs(v):
    for w in graph[v]:
        cnt[w-1] += cnt[v-1]
        graph[w].remove(v)
        if len(graph[w]) > 0:
            dfs(w)
 
dfs(1)
 
print(*cnt)

### FIXED CODE ###

a=int(input())
s=input()
if a>=3200:
    print(s)
else:
    print('red')
import sys

def main():
    input = sys.stdin.readline

    _, _, m = input().split()
    m = int(m)
    alist = input().split()
    blist = input().split()

    waribiki = [input().split() for _ in range(m)]
    
    res = [20000] * (len(alist)*len(blist) + m)
    count = 0
    for a in alist:
      for b in blist:
        res[count] = int(a) + int(b)
        count += 1

    for i in range(m):
        try:
            res[count] = int(alist[int(waribiki[i][0])-1]) + int(blist[int(waribiki[i][1])-1]) - int(waribiki[i][2])
        except Exception:
            res[count] = 20000
        count += 1
      
    print(min(res))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline

    a, b, m = input().split()
    a, b, m = int(a), int(b), int(m)
    alist = list(map(int, input().split()))
    blist = list(map(int, input().split()))

    waribiki = [input().split() for _ in range(m)]
    
    res = [200000] * (m + 1)
    count = 0

    for i in range(m):
        res[count] = alist[int(waribiki[i][0])-1] + blist[int(waribiki[i][1])-1] - int(waribiki[i][2])
        count += 1

    res[count] = min(alist) + min(blist)
      
    print(min(res))


if __name__ == '__main__':
    main()
def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ???????????§?????????????????????-> ?°????????????????????¶???????????????????
    3. 2????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee
    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    # 2.
    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])

    # 3.
    result = ''
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))
            result = result + str(coin_values[i]) + ' ' + str(use_coins[i]) + '\n'
            # return result


if __name__ == "__main__":

    # check_testcase()
    total_fee = int(input('total_fee:'))

    while (True):
        if total_fee == 0: break
        coins = input('total_coins:')
        coins = coins.split(' ')  # 10, 50, 100, 500????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)

### FIXED CODE ###

import math
def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ?????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ????????????§?????????????????????-> ??°?????????????????????¶???????????????????
    3. 2?????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee

    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)
 
    # 2.
    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])
 
    # 3.
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))
 
if __name__ == "__main__":
    first = True
    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        if first:
            first = False
        else:
            print('')
        coins = input('')
        coins = coins.split(' ')  # 10, 50, 100, 500?????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)
import sys
import math
from collections import Counter

mod = 1000000007
 
N = int(sys.stdin.readline().strip())
fishes = []
zero = 0
zero_l = 0
zero_r = 0
rest = N
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())
    # 角度だけが重要なので座標圧縮して良い
    if a == 0 and b == 0:
        # fishes.append((0, 0))
        zero += 1
        rest -= 1
    elif a == 0:
        # fishes.append((0, 1))
        zero_l += 1
    elif b == 0:
        # fishes.append((1, 0))
        zero_r += 1
    else:
        gcd = math.gcd(a, b)
        fishes.append((a // gcd, b // gcd))

# print(fishes)

# (a, b)ごとにカウント
counter = Counter(fishes)
# print(counter)

calculated = set()
ans = 1
# 組み合わせを計算
for ((a, b), count) in counter.items():
    # if a == 0 or b == 0:
    #     continue
    # 計算済みの場合
    if (a, b) in calculated:
        continue

    # 仲が悪いイワシの数
    bad_count = 0
    # 90度異なるものがダメ
    for (a_k, b_k) in ((-1, 1), (1, -1)):
        bad_pair = (b * a_k, a * b_k)
        if bad_pair in counter:
            bad_count += counter[bad_pair]
            calculated.add(bad_pair)

    if bad_count != 0:
        # good か bad からしか選ばないものは駄目
        ans *= pow(2, count + bad_count, mod) - (pow(2, count, mod) - 1) * (pow(2, bad_count, mod) - 1) 
        ans %= mod

        rest -= count + bad_count

# どちらかが0になっているもの
ans *= pow(2, zero_r + zero_l, mod) - (pow(2, zero_l, mod) - 1) * (pow(2, zero_r, mod) - 1)
ans %= mod
rest -= zero_r + zero_l

# 仲が悪いものが存在しないイワシの組み合わせ
ans *= pow(2, rest, mod)

# 全部選ばないものは駄目
ans += zero - 1
ans %= mod

print(ans)

### FIXED CODE ###

import sys
import math
from math import gcd

mod = 1000000007
 
N = int(sys.stdin.readline().strip())
zero = 0
mp = {}
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())

    if a == 0 and b == 0:
        zero += 1
        continue
 
    g = gcd(a, b)
    a = a // g
    b = b // g
 
    if b < 0:
        a = -a
        b = -b
    if b == 0 and a < 0:
        a = -a
    if a <= 0:
        a, b = b, -a
        if (a, b) in mp:
            mp[(a, b)][0] += 1
        else:
            mp[(a, b)] = [1, 0]
    else:
        if (a, b) in mp:
            mp[(a, b)][1] += 1
        else:
            mp[(a, b)] = [0, 1]
 
ans = 1
for key in mp:
    s, t = mp[key]
    ans *= pow(2, s, mod) + pow(2, t, mod) - 1
    ans %= mod
print((zero - 1 + ans) % mod)
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    from math import gcd
    N=I()
    ans=1
    for i in range(N):
        T=I()
        ans=(ans*T)//(gcd(ans,T))
        
        
    print(ans)

main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
from fractions import gcd

def main():
    mod=10**9+7
    N=I()
    ans=1
    for i in range(N):
        t=I()
        ans=(ans*t)//gcd(ans,t)
        
    print(ans)

main()