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

import sys

# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
# import heapq
import bisect


# def input():
#     return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    mod = 10 ** 9 + 7

    #    print(A)
    #    print(A_plus)
    #    print(A_minus)
    if N == K:
        ans = 1
        for i in range(K):
            ans *= A[i] % mod
        print(ans % mod)

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)] % mod
        print(ans % mod)

    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
# import heapq
import bisect


# def input():
#     return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    mod = 10 ** 9 + 7

    if N == K:
        ans = 1
        for i in range(N):
            ans *= A[i]
            ans %= mod
        print(ans % mod)



    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)]
            ans %= mod
        print(ans % mod)
    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


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

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    for i in range(k):
        num=[0]*(n+1)
        for j in range(n):
            num[max(0,j-a[j])]+=1
            num[min(n,j+a[j]+1)]-=1
        num5=0
        for j in range(n):
            num5+=num[j]
            ans[j]=num5
        a=ans
    print(*a)


### FIXED CODE ###

import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    def c(num1,num2,num3):
        num[max(0,num1-num2)]+=1
        num[min(num3,num1+num2+1)]-=1
    for i in range(k):
        num=[0]*(n+1)
        for j in range(n):
            c(j,a[j],n)
        num5=0
        for j in range(n):
            num5+=num[j]
            a[j]=num5
        if sum(a)==n*n:
            break
    print(*a)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
#start = time.clock()
#i = 0
n=input()
S=map(int, raw_input().split())
q=input()
T=map(int, raw_input().split())
s=sorted(set(S), key=S.index)
st=set(s)-set(T)
ST=list(st)
print len(s)-len(ST)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
n=input()
S=map(int, raw_input().split())
q=input()
T=map(int, raw_input().split())
#s=sorted(set(S), key=S.index)
print len(set(S)&set(T))
### BUGGY CODE ###

N = int(input())

A = list(map(int, input().split()))
sum=1
for n in A:
    sum=sum*n

if sum>pow(10,18):
    sum = -1

print(sum)




### FIXED CODE ###


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

if 0 in A:
    print(0)
else:
    for n in range(N):
        sum = sum * A[n]
        if sum>1000000000000000000:
            print(-1)
            break
    else:
        print(sum)
### BUGGY CODE ###

import sys
import math
input = sys.stdin.readline


def main():
    sc = Scan()
    N = sc.intarr()[0]
    S = sc.strarr()[0]

    count = 0

    for i in range(1000):
        # print("--------")
        lucky = format_str(i)
        Flag_j, Flag_m, Flag_n = -1, -1, -1
        # print("check001")

        for j in range(N-2):
            if S[j] == lucky[0]:
                Flag_j = j
                break
        # print("check002")
        if Flag_j == -1:
            continue
        # print("check003")

        for m in range(Flag_j+1, N-1):
            if S[m] == lucky[1]:
                Flag_m = m
                break
        # print("check004")
        if Flag_m == -1:
            continue
        # print("check005")

        for n in range(Flag_m+1, N):
            if S[n] == lucky[2]:
                Flag_n = n
                break
        # print("check006")
        if Flag_n == -1:
            continue
        # print("check007")
        count += 1

    print(count)


def format_str(num):
    if num < 10:
        return "00" + str(num)
    elif num < 100:
        return "0" + str(num)
    else:
        return str(num)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


main()


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline


def main():
    sc = Scan()
    _ = sc.intarr()[0]
    S = sc.strarr()[0]

    count = 0

    for i in range(1000):
        # print("--------")
        lucky = format_str(i)
        first = S.find(lucky[0])
        third = S.rfind(lucky[2])

        if first == -1 or third == -1:
            continue
        elif first < third:
            if lucky[1] in S[first + 1:third]:
                count += 1
    print(count)


def format_str(num):
    if num < 10:
        return "00" + str(num)
    elif num < 100:
        return "0" + str(num)
    else:
        return str(num)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


main()
### BUGGY CODE ###

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

for _ in range(int(n / k) + 1):
    if abs(n - k) < n:
        n = abs(n - k)
    else:
        break

print(n)

### FIXED CODE ###

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

a = n % k
print(min(a, abs(a - k)))
### BUGGY CODE ###

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

ans = [0]*n
for i in range(n):
    for j in range(i, n-1):
        if h[j] >= h[j+1]:
            ans[i] += 1
        else:
            break
print(max(ans))


### FIXED CODE ###

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

cnt = 0
ans = 0
for i in range(n-1):
        if h[i] >= h[i+1]:
            cnt += 1
        else:
            ans = max(ans, cnt)
            cnt = 0
print(max(ans, cnt))
### BUGGY CODE ###

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

d = 'YES'

for i in range(n):
  if a.count(a[i]) > 1:
    d = 'NO'
    break

print(d)

### FIXED CODE ###

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

b = set(a)

if len(a) == len(b):
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

S = input()
Q = int(input())
reverse = False
for _ in range(Q):
    cmd = input().split()
    if cmd[0] == "1":
        reverse = not reverse
    else:
        top = (cmd[1] == "1") ^ reverse
        S = cmd[2] + S if top else S + cmd[2]
print(S[::-1]) if reverse else print(S)

### FIXED CODE ###

S = input()
Q = int(input())
head, tail = "", ""
reverse = False
for _ in range(Q):
    cmd = input().split()
    if cmd[0] == "1":
        reverse = not reverse
    else:
        top = (cmd[1] == "1") ^ reverse
        if top:
            head += cmd[2]
        else:
            tail += cmd[2]
print(tail[::-1] + S[::-1] + head) if reverse else print(head[::-1] + S + tail)
### BUGGY CODE ###

if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))

    bosses = []
    for n in range(1, N+1):
        bosses.append(As.count(n))
    
    print("\n".join(map(str, bosses)))

### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))

    bosses = [0]*N
    for a in As:
        bosses[a-1] = bosses[a-1] + 1
    
    print("\n".join(map(str, bosses)))
### BUGGY CODE ###

N = int(input())
#a = [1,6,36,216,1296,7776,46656]
#b = [1,9,81,729,6561,59049]
c = [0]
n = 1
while n <= N:
  if n == 1:
    c.append(1)
    n += 1
  elif n < 6:
    c.append(1+c[n-1])
    n += 1
  elif n < 9:
    c.append(1+min(c[n-1],c[n-6]))
    n += 1
  elif n < 36:
    c.append(1+min(c[n-1],c[n-6],c[n-9]))
    n += 1
  elif n < 81:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36]))
    n += 1
  elif n < 216:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81]))
    n += 1
  elif n < 729:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216]))
  elif n < 1296:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729]))
  elif n < 6561:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729],c[n-1296]))
  elif n < 7776:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729],c[n-1296],c[n-6561]))
  elif n < 46656:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729],c[n-1296],c[n-6561],c[n-7776]))
  elif n < 59049:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729],c[n-1296],c[n-6561],c[n-7776],c[n-46656]))
  else:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729],c[n-1296],c[n-6561],c[n-7776],c[n-46656],c[n-59049]))
print(c[N])

### FIXED CODE ###

N = int(input())
def cn(X, n):
    if (int(X/n)):
        return cn(int(X/n), n)+str(X%n)
    return str(X%n)
def su(n):
  ans = 0
  for chara in n:
    ans += int(chara)
  return ans
lis = []
i = 0
while i <= N:
  lis.append(su(cn(i,6))+su(cn(N-i,9)))
  i += 1
print(min(lis))
### BUGGY CODE ###

N, M = map(int, input().split())
cities = {}
P = {}
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = (p,y)
    if not p in P:
        P[p] = [y]
    else:
        P[p].append(y)

sorted_P = {p:sorted(P[p]) for p in P}

for i in range(M):
    city_p, city_y = cities[i]
    x = sorted_P[city_p].index(city_y)+1
    print('{0:06}{1:06}'.format(city_p, x))


### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
cities = {}
P = {}
Y = {}
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = p
    Y[i] = y

ans = {}
sorted_Y = sorted(Y.items(), key=lambda x:x[1])
P_i = np.zeros(N)
for i,y in sorted_Y:
    p = cities[i]
    P_i[p-1] += 1
    ans[i] = (p, int(P_i[p-1]))

for i in range(M):
    print('{0:06}{1:06}'.format(ans[i][0], ans[i][1]))
### BUGGY CODE ###

S=input()
T=input()
Skey,Tkey=[],[]
for i in range(len(S)):
  Skey.append(S[i])
  Tkey.append(T[i])

for index,i in enumerate(Skey):
  S=S.replace(i,str(index))
for index,i in enumerate(Tkey):
  T=T.replace(i,str(index))

if S==T:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

S = input()
T = input()

Skey = sorted(set(S),key=S.index)
Tkey = sorted(set(T),key=T.index)

for idx,i in enumerate(Skey):
  S = S.replace(i,str(idx))
for idx,i in enumerate(Tkey):
  T = T.replace(i,str(idx))

if S==T:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

s = input()
n = int(input())

ct = 0

for i in range(n):
    p = input().split()

    if p[0] == '1':
        ct += 1
    else:
        if ct % 2 != 0:
            s = s[::-1]
        ct = 0
        
        if p[1] == "1":
            s = p[2] + s
        else:
            s = s + p[2] 
    
if ct % 2 != 0:
    s = s[::-1]

print(s)

### FIXED CODE ###

S = input()
Q = int(input())

dire = 0
front = ""
back = ""

for i in range(Q):
    quary = [_ for _ in input().split()]
    if len(quary) == 1:
        T = quary[0]
        dire += 1
    else:
        T, F, C = quary
        if F == "1":
            if dire % 2 == 0:
                front += C
            else:
                back += C
        else:
            if dire % 2 == 1:
                front += C
            else:
                back += C

S = front[::-1] + S + back

if dire % 2 == 1:
    print(S[::-1])
else:
    print(S)
### BUGGY CODE ###

s = input()
ans = 0
for i in range(len(s)):
    a = int(s[i:])
    while a > 1000:
        if a % 2019 == 0:
            ans += 1
        a //= 10
print(ans)

### FIXED CODE ###

s = input()
l = []
n = len(s)
mod = 2019
s = list(s)
s = list(map(int, s))
l.append(s[-1])
for i in range(n-2, -1, -1):
    tmp = l[-1]
    l.append((tmp+s[i] * pow(10, n - i - 1, 2019))%2019)
cnt = [0 for i in range(2019)]
cnt[0] += 1
for i in range(len(l)):
    cnt[l[i]] += 1
ans = 0
for i in range(len(cnt)):
    ans += cnt[i]*(cnt[i]-1)//2
print(ans)
### BUGGY CODE ###

N= int(input())
A=[int(i) for i in input().split()]

from  heapq import heappush, heappop

hq=[]
for i in range(N):
    heappush(hq, (A[i],i))

ans=""
for i in range(N):
    ans=ans+str(heappop(hq)[1]+1)+" "
print(ans[:-1])




### FIXED CODE ###


N= int(input())
A=[[int(i), ind] for ind, i in enumerate(input().split())]

A=sorted(A)
for i in range(N-1):
    print(A[i][1]+1, end=" ")
print(A[N-1][1]+1)
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = ['']*N
    for i in range(N):
        ans[i] = str(A.count(i+1))
    print('\n'.join(ans))
resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    import collections
    c = collections.Counter(A)
    for i in range(1,N+1):
        print(c[i])
resolve()
### BUGGY CODE ###

N = int(input())
S = input()

moves = 2 * 10 ** 5

for i in range(len(S) + 1):
    left = S[:i]
    right = S[i:]
    moves = min(moves, left.count('#') + right.count('.'))

print(moves)


### FIXED CODE ###

N = int(input())
S = input()

w = S.count('.')
b = 0

k = w

for i in range(N):
    if S[i] == '.':
        w -= 1
    else:
        b += 1

    k = min(k, w + b)

print(k)
### BUGGY CODE ###

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

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

def gcd_of_arr(arr):
    cd = arr[0]
    for i in range(1,len(arr)):
        if cd==1:
            return cd
        cd = gcd(arr[i], cd)
    return cd

B = [0]*N
for i in range(N):
    tmp = A[0:i] + A[i+1:N]
    B[i] = gcd_of_arr(tmp)

print(max(B))


### FIXED CODE ###

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

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

L, R = [0]*(N+1), [0]*(N+1)
for i in range(1,N+1):
    L[i] = gcd(L[i-1], A[i-1])
    R[N-i] = gcd(R[N+1-i], A[N-i])

ans = 0
for i in range(N):
    ans = max(ans, gcd(L[i], R[i+1]))

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

from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)
dp = [[[-1] * 2 for _ in range(n)] for _ in range(n + 1)]

def dfs(u, pu=-1):
    if dp[pu][u][0] != -1:
        return dp[pu][u]
    w = b = 1
    for v in to[u]:
        if v == pu: continue
        vb, vw = dfs(v, u)
        b += b * vb
        w += vb + vw - 1
        b, w = b % m, w % m
    dp[pu][u] = [b, w]
    return [b, w]

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    for u in range(n):
        print(dfs(u)[0])

main()


### FIXED CODE ###

from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)
# dp[u][v] uを根としたときのサブツリーvの値
dp = {}

def dfs(u=0, pu=-1):
    res = 1
    for v in to[u]:
        if v == pu: continue
        res *= dfs(v, u) + 1
        res %= m
    if pu != -1: dp[(pu,u)] = res
    return res

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    dfs()
    # bfsでdfsとは逆向きのdpを完成させる
    que = deque()
    que.append([0, -1])
    while que:
        u, pu = que.popleft()
        tn = len(to[u])
        # 累積積のための配列
        ll = [0] * tn
        rr = [0] * tn
        # uのサブツリーの値+1を入れる
        for i, v in enumerate(to[u]):
            ll[i] = rr[i] = dp[(u,v)] + 1
        # 左右から累積積を作る
        for i in range(1, tn):
            ll[i] = (ll[i - 1] * ll[i]) % m
            rr[tn - 1 - i] = (rr[tn - i] * rr[tn - 1 - i]) % m
        # 配列の最初or最後のために最後に1を追加
        ll += [1]
        rr += [1]
        # uの子vを根とみたときのサブツリーuの値を求める
        for i, v in enumerate(to[u]):
            if v == pu: continue
            dp[(v,u)] = (ll[i - 1] * rr[i + 1]) % m
            que.append([v, u])
    # p2D(dp)
    # 各頂点について答えを出す
    for u in range(n):
        ans = 1
        for v in to[u]:
            ans = (ans * (dp[(u,v)] + 1)) % m
        print(ans)

main()
### BUGGY CODE ###

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
counts = [[[-1] * w for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        if ls[y][x] == '#':
            counts[0][y][x] = 0
        else:
            if x == 0:
                counts[0][y][x] = 1
            else:
                counts[0][y][x] = counts[0][y][x - 1] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[1][yy][xx] = 0
        else:
            if x == 0:
                counts[1][yy][xx] = 1
            else:
                counts[1][yy][xx] = counts[1][yy][xx + 1] + 1
for x in range(w):
    for y in range(h):
        if ls[y][x] == '#':
            counts[2][y][x] = 0
        else:
            if y == 0:
                counts[2][y][x] = 1
            else:
                counts[2][y][x] = counts[2][y - 1][x] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[3][yy][xx] = 0
        else:
            if y == 0:
                counts[3][yy][xx] = 1
            else:
                counts[3][yy][xx] = counts[3][yy + 1][xx] + 1

res = 0
for y in range(h):
    for x in range(w):
        val = -3
        for i in range(4):
            val += counts[i][y][x]
        res = max(res, val)

print(res)

### FIXED CODE ###

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
counts = [[[-1] * w for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        if ls[y][x] == '#':
            counts[0][y][x] = 0
        else:
            if x == 0:
                counts[0][y][x] = 1
            else:
                counts[0][y][x] = counts[0][y][x - 1] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[1][yy][xx] = 0
        else:
            if x == 0:
                counts[1][yy][xx] = 1
            else:
                counts[1][yy][xx] = counts[1][yy][xx + 1] + 1

        if ls[y][x] == '#':
            counts[2][y][x] = 0
        else:
            if y == 0:
                counts[2][y][x] = 1
            else:
                counts[2][y][x] = counts[2][y - 1][x] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[3][yy][xx] = 0
        else:
            if y == 0:
                counts[3][yy][xx] = 1
            else:
                counts[3][yy][xx] = counts[3][yy + 1][xx] + 1

res = 0
for y in range(h):
    for x in range(w):
        val = -3
        for i in range(4):
            val += counts[i][y][x]
        res = max(res, val)

print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
from fractions import gcd

if n==1:
    print(1)
else:
    g=A[0]
    l=A[0]
    for i in range(n-1):
        g=gcd(l,A[i+1])
        l*=(A[i+1]//g)
    ans=0
    for i in range(n):
        ans+=(l//A[i])%mod        
    print(ans%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from fractions import gcd
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
def gyaku(a):
    return pow(a,mod-2,mod)
if n==1:
    print(1)
else:
    gya=[0]*(n)
    g=A[0]
    l=A[0]
    gya[0]=gyaku(A[0])
    for i in range(n-1):
        g=gcd(l,A[i+1])
        l*=(A[i+1]//g)
        gya[i+1]=gyaku(A[i+1])
    ans=0
    for i in range(n):
        ans+=l*gya[i]
        ans%=mod
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from itertools import accumulate
import numpy as np
MOD = 1000000007  # type: int


def solve(N: int, s: str):

    # DP[i][j]はi文字目までをみたす順列のうち、最後がjで終わるものの個数
    DP = np.zeros((N, N+1), dtype=np.int64)
    # DP = [[0]*(N+1) for _ in range(N)]
    DP[0][1] = 1

    for i in range(1, N):
        acc = list(accumulate(DP[i-1]))
        for j in range(1, (i+1)+1):
            if s[i-1] == "<":
                DP[i][j] = acc[j-1]
            else:
                DP[i][j] = acc[i+1] - acc[j-1]
            DP[i][j] %= MOD

    print(sum(DP[N-1]) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = next(tokens)  # type: str
    solve(N, s)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, s: str):

    # DP[i][j]はi文字目までをみたす順列のうち、最後がjで終わるものの個数
    DP = [[0]*(N+1) for _ in range(N)]
    DP[0][1] = 1

    for i in range(1, N):
        acc = list(accumulate(DP[i-1]))
        for j in range(1, (i+1)+1):
            if s[i-1] == "<":
                DP[i][j] = acc[j-1]
            else:
                DP[i][j] = acc[i+1] - acc[j-1]
            DP[i][j] %= MOD

    print(sum(DP[N-1]) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = next(tokens)  # type: str
    solve(N, s)


if __name__ == '__main__':
    main()