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

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class SegmentTree:
    def __init__(self, S):
        N = len(S)
        d = N.bit_length()
        T = [0 for _ in range(2 ** (d + 1) - 1)]
        for i, s in enumerate(S):
            T[i + 2 ** d - 1] = 1 << s
        for i in range(2 ** d - 2, -1, -1):
            T[i] = T[2 * i + 1] | T[2 * i + 2]
        self.d = d
        self.T = T

    def update(self, i, a):
            i = i + 2 ** self.d - 1
            while i > 0:
                i = (i - 1) // 2
                self.T[i] = self.T[2 * i + 1] | self.T[2 * i + 2]
    
    def query(self, a, b):
        return self._query(a, b, 0, 0, 2 ** self.d)

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0

        if a <= l and r <= b:
            return self.T[k]
        else:
            s1 = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
            s2 = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
            return s1 | s2


def main():
    N, Q = read_values()
    C = read_list()

    ST = SegmentTree(C)
    for _ in range(Q):
        a, b = read_index()
        print(format(ST.query(a, b + 1), "b").count("1"))


if __name__ == "__main__":
    main()



### FIXED CODE ###

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class BIT:
    def __init__(self, N):
        self.N = N
        self.T = [0] * (N + 1)

    def add(self, i, x):
        i += 1
        while i <= self.N:
            self.T[i] += x
            i += i & -i

    def _sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.T[i]
            i -= i & -i
        return s

    def sum(self, i, j):
        si = self._sum(i - 1)
        sj = self._sum(j)
        return sj - si
    

def main():
    N, M = read_values()
    C = read_list()
    Q = []
    for i in range(M):
        l, r = read_index()
        Q.append((l, r, i))
    Q.sort(key=lambda a: a[1])

    ans = [0] * M
    T = [-1] * M
    bit = BIT(N)
    q = 0
    # print(Q)
    for i in range(N):
        c = C[i] - 1
        t = T[c]
        if t != -1:
            bit.add(t, -1)
        T[c] = i
        bit.add(i, 1)

        # print(i, T, bit.T)
        while q < len(Q) and i == Q[q][1]:
            l, r, k = Q[q]
            ans[k] = bit.sum(l, r)
            q += 1

    print("\n".join(map(str, ans))) 

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

S = input()
def co(s):
    l = list(s)
    cnt = True
    for i in range(len(s))[:0:-1]:
        if l[i] != l[i-1]:
            del l[i]
            del l[i-1]
            cnt = False
            break
    if cnt:
        return s
    if not cnt:
        return co(''.join(l))
print(len(S)-len(co(S)))

### FIXED CODE ###

s = input()
l = list(s)
print(len(s)-abs(l.count('0')-l.count('1')))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
res = 0
Ab = [True] * N
cnt = 0
for i in range(N):
    if Ab[i]:
        for j in range(i+1,N):
            if Ab[j] :
                if A[j] % A[i] == 0:
                     Ab[j] = False
                     if A[i] == A[j]:
                        Ab[i] = False
print(Ab.count(True))



### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)
### BUGGY CODE ###

A, B = map(int, input().split())

ans = 0
for n in range(A, B+1):
    ans = ans ^ n

print(ans)


### FIXED CODE ###

import math

A, B = map(int, input().split())


def f(num):
    n_max = math.ceil(math.log2(num+1))
    result = 0
    for n in range(n_max):
        if n == 0:
            r = num % 4
            if r == 1 or r == 2:
                result += 1
            continue
        r = (num+1) % 2**(n+1)
        if r <= 2**n:
            continue
        else:
            r -= 2**n

        if r % 2 == 1:
            result += 2**n

    return result


if A > 0:
    print(f(A-1) ^ f(B))
else:
    print(f(B))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read

n,*X=map(int,read().split())
mod = 10**9+7
last=X[-1]
X=[last-i for i in X[:-1]]
l=1
left=[1]
for i in range(1, n-1):
  l=l*i%mod
  left.append(l)
r=1
right=[1]
for i in range(n-1, 1, -1):
  r*=i%mod
  right.append(r)
right.reverse()
flst=[]
for i,j in zip(left,right):
  flst.append(i*j%mod)
s=0
for i,j in zip(X,flst):
  s+=i*j%mod
print(s%mod)

### FIXED CODE ###

# https://atcoder.jp/contests/dwacon6th-prelims/submissions/9426910


def solve():
    MOD = 10**9 + 7

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

    ds = []
    for i in range(N-1):
        d = xs[i+1] - xs[i]
        ds.append(d)

    nums = [1, 1]
    num = 1
    for i in range(2, N-1):
        num *= i
        num %= MOD
        nums.append(num)

    ms = [N-1]
    m = N-1
    for i in reversed(range(2, N-1)):
        m *= i
        m %= MOD
        ms.append(m)
    ms.reverse()
    ms.append(1)

    ks = []
    k = 0
    for num, m in zip(nums, ms):
        k += num*m % MOD
        k %= MOD
        ks.append(k)

    ans = 0
    for d, k in zip(ds, ks):
        ans += d*k % MOD
        ans %= MOD

    print(ans)

solve()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

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

a_cs = [0] * (n + 1)
a_cs[-2] = a[-1]
for i in reversed(range(n - 1)):
    a_cs[i] = a[i] + a_cs[i + 2]
# print(a_cs)


def func(i):
    if i == n:
        return 0
    if i == n - 1:
        return a[-1]

    m = n - i
    if m % 2 == 0:
        ans0 = a[i] + func(i + 2)
        ans1 = a_cs[i + 1]
        ans = max(ans0, ans1)
    else:
        ans0 = a[i + 0] + func(i + 2)
        ans1 = a[i + 1] + func(i + 3)
        ans2 = a_cs[i + 2]
        ans = max(ans0, ans1, ans2)

    return ans


ans = func(0)

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

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

a_cs = [0] * (n + 1)
a_cs[-2] = a[-1]
for i in reversed(range(n - 1)):
    a_cs[i] = a[i] + a_cs[i + 2]
# print(a_cs)

d = {}


def func(i):
    if i == n:
        return 0
    if i == n - 1:
        return a[-1]
    if i in d:
        return d[i]

    m = n - i
    if m % 2 == 0:
        ans0 = a[i] + func(i + 2)
        ans1 = a_cs[i + 1]
        ans = max(ans0, ans1)
    else:
        ans0 = a[i + 0] + func(i + 2)
        ans1 = a[i + 1] + func(i + 3)
        ans2 = a_cs[i + 2]
        ans = max(ans0, ans1, ans2)

    d[i] = ans
    return ans


ans = func(0)

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

n,m=map(int,input().split())
templ=[0]*m
temp=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append([b,n])
if len(temp)>=1 and ans==0:
  c = [x for x in temp if x in templ]
  if len(c)>=1:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")
else:
  print("IMPOSSIBLE")            
    

### FIXED CODE ###

n,m=map(int,input().split())
templ=[0]*m
temp=[]
tempb=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append(b)
  if b==n:
    tempb.append(a)
if len(temp)>=1 and ans==0:
  temp=set(temp)
  tempb=set(tempb)
  c = temp&tempb
  #c = [x for x in temp if x in tempb]
  if len(c)>=1:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")
  """
  for i in range(0,len(tempb)):
    if tempb[i] in temp:
      print("POSSIBLE")
      break
  """
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

s=input()
l=len(s)
amari=[0]*2019
amari[0]=1

d=0
digi=1

for c in s[::-1]:
    d=(int(c)*digi + d)%2019
    amari[d]+=1
    digi=(digi*10)

ans=0
for i in amari:
    ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

s=input()
l=len(s)
amari=[0]*2019
amari[0]=1

d=0
digi=1

for c in s[::-1]:
    d=(int(c)*digi + d)%2019
    amari[d]+=1
    digi=(digi*10)%2019

ans=0
for i in amari:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

def fib(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

n = int(input())
print(fib(n))

### FIXED CODE ###

def fib(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    if F[n] > 0:
        return F[n]
    F[n] = fib(n-1) + fib(n-2)
    return F[n]

n = int(input())
F = [0 for i in range(n+1)]
print(fib(n))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(65536)

N,M=map(int, input().split())
bridge=[[int(x) for x in input().split()] for _ in range(M)]

uf=[i for i in range(N+1)]
nc=[1 for i in range(N+1)]

def find(i):
	if uf[i] == i:
		return i
	else:
		uf[i] = find(uf[i])
		return uf[i]

def union(i, j):
	gi, gj = find(i), find(j)
	if gi != gj:
		uf[gi] = gj
		diff = nc[gj] * nc[gi]
		nc[gj] += nc[gi]
		return diff
	return 0

su = N*(N-1)//2
ans = [-1]*M

for i in range(M-1, -1, -1):
	ans[i] = su
	x,y = bridge[i]
	su -= union(x, y)

for p in ans:
	print(p)


### FIXED CODE ###

import sys
sys.setrecursionlimit(65536)

N,M=map(int, input().split())
bridge=[[int(x) for x in input().split()] for _ in range(M)]

uf=[i for i in range(N+1)]
nc=[1 for i in range(N+1)]

def find(i):
	if uf[i] == i:
		return i
	else:
		uf[i] = find(uf[i])
		return uf[i]

def union(i, j):
	gi, gj = find(i), find(j)
	if gi != gj:
		uf[gi] = gj
		diff = nc[gj] * nc[gi]
		nc[gj] += nc[gi]
		return diff
	return 0

su = N*(N-1)//2
ans = [-1]*M

for i in range(M-1, -1, -1):
	ans[i] = su
	x,y = bridge[i]
	su -= union(x, y)

print("\n".join(map(str, ans)))
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


class UF:
    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def get_parent(self, a):
        p = self.parent[a]
        if a == p:
            return a

        q = self.get_parent(p)
        self.parent[a] = q
        return q

    def make_pare(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa != pb:
            self.parent[pa] = pb
            self.parent[a] = pb

    def is_pare(self, a, b):
        return self.get_parent(a) == self.get_parent(b)


def main():
    N, M = read_values()
    P = read_list()
    F = [0] * N
    for i, p in enumerate(P):
        F[p - 1] = i

    W = [tuple(read_values()) for _ in range(M)]
    U = UF(N)
    for a, b in W:
        a -= 1
        b -= 1
        U.make_pare(a, b)

    res = 0
    already = [False] * N
    for i in range(N):
        if already[i]:
            continue

        S_num = {i}
        S_index = {F[i]}
        for j in range(i + 1, N):
            if already[j]:
                continue

            if U.is_pare(i, j):
                S_num.add(j)
                S_index.add(F[j])
                already[j] = True
        res += len(S_num & S_index)
    print(res)


if __name__ == "__main__":
    main()



### FIXED CODE ###

import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


class UF:
    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def get_parent(self, a):
        p = self.parent[a]
        if a == p:
            return a

        q = self.get_parent(p)
        self.parent[a] = q
        return q

    def make_pare(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa != pb:
            self.parent[pa] = pb
            self.parent[a] = pb

    def is_pare(self, a, b):
        return self.get_parent(a) == self.get_parent(b)


def main():
    N, M = read_values()
    P = read_list()
    F = [0] * N

    W = [tuple(read_values()) for _ in range(M)]
    U = UF(N)
    for a, b in W:
        a -= 1
        b -= 1
        U.make_pare(a, b)

    res = 0
    for p in P:
        p -= 1
        if U.is_pare(p, P[p] - 1):
            res += 1
    print(res)


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

import numpy as np
n, k = map(int, input().split())
h = []
for _ in range(n):
    h.append(int(input()))
h = np.array(sorted(h))
diff = np.diff(h)
low_score = np.inf
for i in range(n - k + 1):
    cost = np.sum(diff[i: i + k - 1])
    low_score = min(low_score, cost)
print(low_score)

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = np.array(sorted([int(input()) for _ in range(n)]))
h_roll = np.roll(h, -k + 1)
x = h_roll - h
print(int(x[:-k + 1].min()))
### BUGGY CODE ###

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

ans = 0
for na in range(n+1):
    for nb in range(m+1):
        time = sum(a[:na]) + sum(b[:nb])
        if time > k:
            break
        ans = max(ans, na+nb)
print(ans)

### FIXED CODE ###

import copy

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

asum = [0]
bsum = [0]
tmp = 0
for i in range(n):
    tmp += a[i]
    asum.append(tmp)
tmp = 0
for i in range(m):
    tmp += b[i]
    bsum.append(tmp)


ans = 0
nb = copy.deepcopy(m)
for na in range(n+1):
    res = k - asum[na]
    if res < 0:
        break
    flg = True
    while flg:
        if bsum[nb] > res:
            nb -= 1
            continue
        ans = max(ans, na+nb)
        break
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
first=list(map(int,input().split()))
for l in range(M):
  first.sort()
  first[N-1]=(first[N-1])/2

second=[]
for _ in range(N):
  second.append(0)
for i in range(N):
  second[i]=int(first[i])
print(sum(second))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
kakaku=list(map(int,input().split()))
han=[]
for i in range(N):
  han.append(-kakaku[i])
  
heapq.heapify(han)
for _ in range(M):
  k=heapq.heappop(han)
  k=k/2
  heapq.heappush(han,k)

sum=0
for j in range(N):
  sum+=int(-han[j])
print(sum)
### BUGGY CODE ###

from collections import deque
xs,yx,xt,yt = map(int,input().split())
N = int(input())
G = [[i for i in range(1,N+3)] for _ in range(N+3)]
l = [[],[xs,yx,0],[xt,yt,0]]
for i in range(N):
  l.append(list(map(int,input().split())))
##距離リスト
d = [[0]*(N+3) for _ in range(N+3)]
for i in range(1,N+3):
  d[i][i] = 0
#O(10**6)
for i in range(1,N+3):
  for j in range(i+1,N+3):
    sa = (l[i][0]-l[j][0])**2 + (l[i][1]-l[j][1])**2
    kyori = max(0,sa**(1/2)-l[i][2]-l[j][2])
    d[i][j] = kyori
    d[j][i] = kyori

md = [float("inf")]*(N+3)
deq = deque([1])
md[1] = 0
while len(deq)>0:
  v = deq.popleft()
  for i in G[v]:
    if md[i] > md[v] + d[v][i]:
      md[i] = md[v] + d[v][i]
      deq.append(i)
print(md[2])      

### FIXED CODE ###

xs,yx,xt,yt = map(int,input().split())
N = int(input())
l = [[],[xs,yx,0],[xt,yt,0]]
for i in range(N):
  l.append(list(map(int,input().split())))
##距離リスト
d = [[0]*(N+3) for _ in range(N+3)]
for i in range(1,N+3):
  d[i][i] = 0
#O(10**6)
for i in range(1,N+3):
  for j in range(i+1,N+3):
    sa = (l[i][0]-l[j][0])**2 + (l[i][1]-l[j][1])**2
    kyori = max(0,sa**(1/2)-l[i][2]-l[j][2])
    d[i][j] = kyori
    d[j][i] = kyori

md = [float("inf")]*(N+3)
h = [i for i in range(1,N+3)]
for i in range(1,N+3):
  md[i]=d[1][i]
seen = [False]*(N+3)
seen[1] = True
while True:
  #vを出す
  v = -1
  for i in h:
    if seen[i] == False and v == -1:
      v = i
    elif seen[i] == False and md[i] < md[v]:
      v = i
  if v == -1:
    break
  seen[v] = True
  for j in range(1,N+3):
    md[j] = min(md[j],md[v]+d[v][j])
print(md[2])
### BUGGY CODE ###

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline

def main():
    n=int(input())
    d=[[]]+[deque(map(int,input().split()))for i in n*[0]]
    immortalskip=set()
    
    c=0
    while any(d):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i in immortalskip:
                continue
            if i not in skip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1
                else:
                    immortalskip.add(i)
                            
        if not f:
            print(-1)
            exit()

    print(c)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline
import time
t=time.time()

def main():
    n=int(input())
    d=[[]]+[deque(map(int,input().split()))for i in n*[0]]

    c=0
    while any(d):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1

        if not f:
            print(-1)
            exit()
        if abs(time.time()-t)>1:
            print(n*(n-1)//2)
            exit()

    print(c)

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

n = input()
s = sorted(list(set(map(int, raw_input().split()))))
q = input()
t = sorted(list(set(map(int, raw_input().split()))))
cnt = 0
for x in s:
    for y in t:
        if x < y: break
        if x == y: cnt += 1
print cnt

### FIXED CODE ###

n = input()
s = list(set(map(int, raw_input().split())))
q = input()
t = list(set(map(int, raw_input().split())))
b = [False] * (10**7+1)
for x in s:
    b[x] = True
cnt = 0
for x in t:
    if b[x]:
        cnt += 1
print cnt
### BUGGY CODE ###

H,W = map(int,input().split())
Ch, Cw = map(int,input().split())
Dh, Dw = map(int,input().split())
S = [list(input()) for _ in range(H)]

INF = H * W

def steppable(h,w):
    if not (h in range(H)) or not (w in range(W)):
        return False
    if S[h][w] == '#':
        return False
    else:
        return True

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop(0) # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        next_  = [
            (h[0] + 1, h[1], 0),
            (h[0] - 1, h[1], 0),
            (h[0], h[1] + 1, 0),
            (h[0], h[1] - 1, 0),]

        for n in next_:
            if steppable(n[0], n[1]) and num_step[n[0]][n[1]] > num_warp:
                queue.append(n)
                num_step[n[0]][n[1]] = num_warp

        # 魔法を使っていける場所を検討
        dx = [-2, -1 , 0, 1, 2]
        dy = [-2, -1 , 0, 1, 2]

        for x in dx:
            for y in dy:
                if steppable(h[0] + y, h[1] + x) and num_step[h[0] + y][h[1] + x] > num_warp:
                    # print(S[h[0] + y][h[1] + x])
                    # print((h[0] + y, h[1] + x))
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] == num_warp
            queue.append((magic[0],magic[1]))

print(-1)

### FIXED CODE ###

H,W = map(int,input().split())
Ch, Cw = map(int,input().split())
Dh, Dw = map(int,input().split())
S = [list(input()) for _ in range(H)]

INF = H * W

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop() # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        for i in range(4):
            if 0 <= h[0]+dy[i] < H and 0 <= h[1]+dx[i] < W and S[h[0]+dy[i]][h[1]+dx[i]] == '.' \
                 and num_step[h[0]+dy[i]][h[1]+dx[i]] > num_warp:
                queue.append((h[0]+dy[i], h[1]+dx[i]))
                num_step[h[0]+dy[i]][h[1]+dx[i]] = num_warp

        # 魔法を使っていける場所を検討
        mx = [-2, -1 , 0, 1, 2]
        my = [-2, -1 , 0, 1, 2]

        for x in mx:
            for y in my:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] = num_warp
            queue.append((magic[0], magic[1]))

print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def l(a, b):
    return a * b // g(a, b)


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B = l(a, B)
    
    print(sum(B // a for a in A) % mod)


if __name__ == "__main__":
    main()



### FIXED CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B *= a // g(B, a)
    
    print(sum(B // a for a in A) % mod)


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

k = int(input())

if k % 2 == 0 or k % 5 == 0:
    print(-1)
    exit()

seven = 7
for _ in range(100000000):
    if seven % k == 0:
        print(len(str(seven)))
        break
    seven = int(str(seven) + "7")

### FIXED CODE ###

k = int(input())
 
s = 7
for i in range(1, k+1):			# rangeの上限がk
    if s % k == 0:
        print(i)
        break
    s = (s * 10 + 7) % k		# %kが難しい
else:                           # for文にもelseが使える
    print(-1)