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

import sys
from math import factorial
from functools import lru_cache

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

def main():
    MOD = 10 ** 9 + 7
    n, a, b = map(int, input().split())

    @lru_cache(maxsize=None)
    def f(n):
        return factorial(n)

    def comb_c(n, r):
        if r > n - r:
            r = n - r 
        a = f(n) % MOD
        b = f(n - r) * f(r)
        return a * pow(b, MOD - 2, MOD) % MOD

    n2 = (n - 1) // 2
    ans = 1
    for i in range(1, n2 + 1):
        ans += comb_c(n, i) * 2
    if n % 2 == 0:
        ans += comb_c(n, n2 + 1)
    ans -= comb_c(n, a)
    ans -= comb_c(n, b)
    ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    MOD = 10 ** 9 + 7
    n, a, b = map(int, input().split())

    def comb_c(n, r):
        if r > n - r:
            r = n - r
        a, b = 1, 1
        for i in range(r):
            a = a * (n - i) % MOD
            b = b * (i + 1) % MOD
        return a * pow(b, MOD-2, MOD)

    ans = pow(2, n, MOD) - 1
    ans -= comb_c(n, a)
    ans -= comb_c(n, b)
    ans %= MOD
    print(ans)

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

N = int(input())
str = input().split()
num_list = []
for i in str:
  num_list.append(int(i))

ans = num_list[0]
LIMIT_NUM = 10**18
for i in range(1,N):
  ans *= num_list[i]

if ans > LIMIT_NUM:
               print(-1)
else:
               print(ans)


### FIXED CODE ###

def main(): 
  N = int(input())
  str_num = input().split()

  num_list = []
  for i in str_num:
    num_list.append(int(i))

  num_list.sort(reverse=True)

  ans = num_list[0]

  LIMIT_NUM = 10**18

  if 0 in num_list:
    print(0)
    return

  for i in range(1,N):
    ans *= num_list[i]
    if ans > LIMIT_NUM:
      print(-1)
      return

  print(ans)


main()
### BUGGY CODE ###

X = int(input())

if X == 1:
    print(0, -1)
    exit()

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

def solve(num, X):
    a = 1
    while a < X:
        if (a) ** 5 - (a -num) ** 5 == X:
            return True, a, a-+ num
        a += 1
    return False, 0, 0

arr = make_divisors(abs(X))
for num in arr:
    flag, a, b = solve(num , X)
    if flag:
        print(a, b)
        exit()
    flag, a, b = solve(-num , X)
    if flag:
        print(a, b)
        exit()

### FIXED CODE ###

X = int(input())

if X == 1:
    print(0, -1)
    exit()

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

def solve(num, X):
    a = 1
    for i in range(1, X+1):
        if (i * 100) ** 5 - (i * 100 - num) ** 5 >= X:
            break
    max_a = 100 * i
    a = max_a - 99
    while a <= max_a:
        if (a) ** 5 - (a -num) ** 5 == X:
            return True, a, a - num
        a += 1
    return False, 0, 0

arr = make_divisors(abs(X))
for num in arr:
    if (num - X) % 5:
        continue
    flag, a, b = solve(num , X)
    if flag:
        print(a, b)
        exit()
    #flag, a, b = solve(-num , X)
    #if flag:
    #    print(a, b)
    #    exit()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
l = [] 
r = []
count = 0

N, M = map(int, input().split())

#idカードの生成
for i in range(0,M):
    l_temp,r_temp = map(int, input().split())
    l.append(l_temp)
    r.append(r_temp)
    
for i in range(1,N+1):
    if max(l) <= i and i <= min(r):
        count += 1

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
l = [] 
r = []
count = 0

N, M = map(int, input().split())
l = [0] * M
r = [0] * M
for i in range(0,M):
    l[i], r[i] = map(int, input().split())

#idカードの生成
    
ml = max(l)
mr = min(r)

for i in range(1,N+1):
    if  ml <= i and i <= mr:
        count += 1

print(count)
### BUGGY CODE ###

import itertools

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

ini = [a[i]*sum(a[i+1:]) for i in range(n)]
print(sum(ini)%(10**9+7))

### FIXED CODE ###

import itertools

n = int(input())
a = list(map(int,input().split()))
s = sum(a)
ini = []
for i in range(n):
    s -= a[i]
    tmp = a[i]*s
    ini.append(tmp)
print(sum(ini)%(10**9+7))
### BUGGY CODE ###

def main():
    s = list(input())
    n = len(s)
    for i in range(n):
        s[i] = int(s[i])
    dp = [[[0 for _ in range(2019)] for _ in range(2)] for _ in range(n+1)]
    for i in range(n):
        for j in range(2019):
            dp[i+1][1][j] += dp[i][0][j]
            dp[i+1][1][j] += dp[i][1][j]
            dp[i+1][0][((j*10)+s[i])%2019] += dp[i][0][j]
        dp[i+1][0][s[i]] += 1
    print(dp[n][0][0]+dp[n][1][0])
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(2019)]
    dp[0] += 1
    x = 0
    for i in range(n):
        x = (x+int(s[n-1-i])*pow(10,i,2019))%2019
        dp[x] += 1
    ans = 0
    for i in range(2019):
        ans += (dp[i]*(dp[i]-1))//2
    print(ans)

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

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
ans=0
for i in range(N):
    ans +=i

print(ans)


### FIXED CODE ###

n = int(input())
print((n*(n-1))//2)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split(" "))
p = np.array(list(map(int, input().split(" "))))
ans = 0
total = 0
for i in range(N - K + 1):
    total = 0
    c = 1
    for k in range(i, i + K):
        total += (p[k] * (p[k] + 1) / 2) * c * np.prod(p[k + 1: i + K])
        c *= p[k]
    ans = max(total / c, ans)
print(ans)

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
ex = [i + 1 for i in p]
ans = sum(ex[0: K])
max_ans = ans
for i in range(K, N):
    ans += ex[i] - ex[i - K]
    max_ans = max(ans, max_ans)
print(max_ans / 2.0)
### BUGGY CODE ###

k, n = [int(elem) for elem in input().split()]
a_lst = [int(elem) for elem in input().split()]

diff = []
for i, a in enumerate(a_lst[:-1]):
    diff.append(a_lst[i+1] - a)
diff.append((a_lst[0] + k) - a_lst[-1])

res = []
for j in range(len(diff)):
    res.append(sum(diff) - diff[j])
print(min(res))

### FIXED CODE ###

k, n = [int(elem) for elem in input().split()]
a_lst = [int(elem) for elem in input().split()]

diff = []
for i, a in enumerate(a_lst[:-1]):
    diff.append(a_lst[i+1] - a)
diff.append((a_lst[0] + k) - a_lst[-1])

res = sum(diff) - max(diff)
print(res)
### BUGGY CODE ###

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

for i in range(m):
  a[a.index(max(a))]//=2
  if a[a.index(max(a))]<1:break
print(sum(a))

### FIXED CODE ###

import heapq
n,m=list(map(int,input().split()))
a=list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(a)
for i in range(m):
  m=heapq.heappop(a)
  heapq.heappush(a, (-m//2)*(-1))
print(-sum(a))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A, B = [0]*N, [0]*N

for i in range(N):
	A[i], B[i] = MAP()

dp = [[INF]*(H+max(A)+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
	for j in range(H+max(A)+1):
		if j-A[i] >= 0:
			dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]]+B[i])
		else:
			dp[i+1][j] = dp[i][j]

print(min(dp[N][H:]))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A = [0]*N
B = [0]*N

for i in range(N):
    A[i], B[i] = MAP()

dp = [[INF]*(H+max(A)+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(H+max(A)):
        if j < A[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]]+B[i])

print(min(dp[N][H:]))
### BUGGY CODE ###

n = int(input())
sum = 0
for i in range (n):
  sum += i
print(sum)
  

### FIXED CODE ###

n = int(input())

print(n*(n-1)//2)
### BUGGY CODE ###

S = input()
K = 13
MOD = 10**9 + 7

dp = [0] * K
dp[0] = 1

for s in S:
    newDp = [0] * K
    if s == '?':
        for i in range(10):
            for j in range(K):
                newDp[(j * 10 + i) % K] += dp[j]
    else:
        i = int(s)
        for j in range(K):
            newDp[(j * 10 + i) % K] += dp[j]
    dp = newDp
    for i in range(K):
        dp[i] %= MOD

print(dp[5])


### FIXED CODE ###

S = input()
MOD = 10**9 + 7
lenS = len(S)

dp = [[0 for _ in range(13)] for _ in range(lenS + 1)]  # dp[digit][d] = digit桁までの mod=d の数
dp[0][0] = 1

digitMask = 1

for digit in range(1, lenS + 1) :
    if(S[-digit] == '?') :
        for d in range(13) :
            for k in range(10) :
                dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - k * digitMask) % 13]) % MOD
    else :
        a = int(S[-digit])
        for d in range(13) :
            dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - a * digitMask) % 13]) % MOD
    digitMask *= 10
    digitMask %= 13

ans = (dp[len(S)][5]) % MOD
print(ans)
### BUGGY CODE ###

from collections import Counter
n, m = map(int, input().split())
l = []
a0 = 0
for i in range(m):
    a = int(input())
    if a - a0 == 0:
        print(0)
        exit()
    l.append(a - a0 - 1)
    a0 = a + 1
l.append(n - a0)
d = Counter(l)
key = list(d.keys())

def cmb(n, r):
    if r > n//2:
        r = n - r
    val = 1
    for i in range(r):
        val *= n - i
        val //= i + 1
    return val

ans = 1
for k in key:
    val = 0
    for i in range(k//2 + 1):
        val += cmb(k - i, i)
    ans *= val**d[k]
    ans %= 10**9 + 7
print(ans)

### FIXED CODE ###

from collections import Counter
n, m = map(int, input().split())
l = []
a0 = 0
for i in range(m):
    a = int(input())
    if a - a0 == 0:
        print(0)
        exit()
    l.append(a - a0 - 1)
    a0 = a + 1
l.append(n - a0)
d = Counter(l)
key = list(d.keys())

ma = max(key)
fib = [1]*(ma + 1)
for i in range(2, ma + 1):
    fib[i] = fib[i - 2] + fib[i - 1]

ans = 1
for k in key:
    ans *= fib[k]**d[k]
    ans %= 10**9 + 7

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

import sys

def MI(): return map(int, sys.stdin.readline().split())

md = 10 ** 9 + 7

n_max = 1005
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
    n, a, b, c, d = MI()
    dp = [0] * (n + 1)
    # dp[j]...i番目の人数の班まで決めて全体でj人が決まったときの場合の数
    dp[0] = 1
    for p in range(a, b + 1):
        for j in range(n, -1, -1):
            dp[j] += sum(dp[j - p * g] * fac[n - j + p * g] * ifac[n - j] * ifac[g] * pow(ifac[p], g, md) for g in
                         range(c, min(j // p, d) + 1))
            dp[j] %= md
    print(dp[n])

main()


### FIXED CODE ###

import sys

def MI(): return map(int, sys.stdin.readline().split())

md = 10 ** 9 + 7

n_max = 1005
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
    n, a, b, c, d = MI()
    pn = b - a + 1  # 班人数の種類数
    dp = [[0] * (n + 1) for _ in range(pn + 1)]
    # dp[i][j]...i番目の人数の班まで決めて全体でj人が決まったときの場合の数
    dp[0][0] = 1
    ps = 0
    for i in range(pn):
        p = i + a  # 班人数
        low = n - (p + b) * (b - p + 1) * d // 2
        up = (a + p - 1) * (p - a) * d // 2
        for j in range(max(low, 0), min(n, up) + 1):
            pre = dp[i][j]
            if pre == 0: continue
            dp[i + 1][j] += pre
            dp[i + 1][j] %= md
            r = n - j  # 残りの人数
            for g in range(c, d + 1):
                if j + p * g > n: break
                dp[i + 1][j + p * g] += pre * fac[r] * ifac[r - p * g] * ifac[g] * pow(ifac[p], g, md)
                dp[i + 1][j + p * g] %= md
        ps += p
    print(dp[pn][n])

main()
### BUGGY CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



sys.setrecursionlimit(10 ** 5 + 10)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1

    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = defaultdict(set)

for _ in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


root = 1
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

### FIXED CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 



sys.setrecursionlimit(10 ** 6)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = [[] for i in range(n + 1)]

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].append(b)
    g[b].append(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)
### BUGGY CODE ###

tmp = input()
L = int(tmp.split(" ")[0])
Q = int(tmp.split(" ")[1])
S = input()
ans = []
preans = 0

for i in range(Q) :
    tmp = input()
    left = int(tmp.split(" ")[0])
    right = int(tmp.split(" ")[1])
    for j in range(left-1,right-1) :
        test = S[j:j+2]
        if test == "AC":
            preans += 1
    ans.append(preans)
    preans = 0

for i in range(Q) :
    print(str(ans[i]))

### FIXED CODE ###

n, q = map(int, input().split())
s = list(input())
ls = len(s)
for i in range(0, ls):
    if (s[i] == "A"):
        if (i != ls-1)and(s[i + 1] == "C"):
            s[i] = "a"

anum = [0]
for i in range(1, ls):
    if (s[i - 1] == "a"):
        anum.append(anum[i - 1] + 1)
    else:
        anum.append(anum[i - 1])

for i in range(q):
    l, r = map(int, input().split())
    print(anum[r-1]-anum[l-1])
### BUGGY CODE ###

in_s = input().rstrip()
s_old = in_s
while True:
    s_new = s_old.replace("10","").replace("01","")
    if s_new == s_old:
        break
    s_old = s_new
print(len(in_s) - len(s_new))

### FIXED CODE ###

in_s = input().rstrip()
lst = list(in_s)
cur=0
while True:
    if cur+1 >= len(lst):
        break
    if lst[cur]!=lst[cur+1]:
        del lst[cur+1]
        del lst[cur]
        cur = max(0,cur-1)
    else:
        cur+=1
 
print(len(in_s) - len(lst))
### BUGGY CODE ###

import heapq

H, W, K=map(int, input().split())
x1, y1, x2, y2=map(int, input().split())
c=['@'*(W+2)]+['@'+input()+'@' for _ in range(H)]+['@'*(W+2)]
l=[[-2]*(W+2) for _ in range(H+2)]
q=[[0, x1, y1]]

heapq.heapify(q)

while q:
  tmp=heapq.heappop(q)
  l[tmp[1]][tmp[2]]=tmp[0]
  
  j=1
  while j<=K and c[tmp[1]-j][tmp[2]]=='.' and l[tmp[1]-j][tmp[2]]==-2:
    heapq.heappush(q, [tmp[0]+1, tmp[1]-j, tmp[2]])
    l[tmp[1]-j][tmp[2]]=-1
    j+=1
  j=1
  while j<=K and c[tmp[1]+j][tmp[2]]=='.':
    if l[tmp[1]+j][tmp[2]]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1]+j, tmp[2]])
      l[tmp[1]+j][tmp[2]]=-1
    j+=1
  j=1
  while j<=K and c[tmp[1]][tmp[2]-j]=='.':
    if l[tmp[1]][tmp[2]-j]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]-j])
      l[tmp[1]][tmp[2]-j]=-1
    j+=1
  j=1
  while j<=K and c[tmp[1]][tmp[2]+j]=='.':
    if l[tmp[1]][tmp[2]+j]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]+j])
      l[tmp[1]][tmp[2]+j]=-1
    j+=1
    
  if l[x2][y2]>=0:
    print(l[x2][y2])
    exit()

if l[x2][y2]<0:
  print(-1)
else:
  print(l[x2][y2])

### FIXED CODE ###

import heapq

H, W, K=map(int, input().split())
x1, y1, x2, y2=map(int, input().split())
c=['@'*(W+2)]+['@'+input()+'@' for _ in range(H)]+['@'*(W+2)]
l=[[-2]*(W+2) for _ in range(H+2)]
ll=[[-2]*(W+2) for _ in range(H+2)]
q=[[0, x1, y1]]

heapq.heapify(q)
ll[x1][y1]=0

while q:
  tmp=heapq.heappop(q)
  if ll[tmp[1]][tmp[2]]==tmp[0]:
    l[tmp[1]][tmp[2]]=tmp[0]
  else:
    continue
  
  j=1
  while j<=K and c[tmp[1]-j][tmp[2]]=='.':
    if l[tmp[1]-j][tmp[2]]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1]-j, tmp[2]])
      l[tmp[1]-j][tmp[2]]=-1
      ll[tmp[1]-j][tmp[2]]=tmp[0]+1
      j+=1
    elif ll[tmp[1]-j][tmp[2]]==tmp[0]+1:
      j+=1
    else:
      j=K+1
    
  j=1
  while j<=K and c[tmp[1]+j][tmp[2]]=='.':
    if l[tmp[1]+j][tmp[2]]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1]+j, tmp[2]])
      l[tmp[1]+j][tmp[2]]=-1
      ll[tmp[1]+j][tmp[2]]=tmp[0]+1
      j+=1
    elif ll[tmp[1]+j][tmp[2]]==tmp[0]+1:
      j+=1
    else:
      j=K+1
      
  j=1
  while j<=K and c[tmp[1]][tmp[2]-j]=='.':
    if l[tmp[1]][tmp[2]-j]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]-j])
      l[tmp[1]][tmp[2]-j]=-1
      ll[tmp[1]][tmp[2]-j]=tmp[0]+1
      j+=1
    elif ll[tmp[1]][tmp[2]-j]==tmp[0]+1:
      j+=1
    else:
      j=K+1
      
  j=1
  while j<=K and c[tmp[1]][tmp[2]+j]=='.':
    if l[tmp[1]][tmp[2]+j]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]+j])
      l[tmp[1]][tmp[2]+j]=-1
      ll[tmp[1]][tmp[2]+j]=tmp[0]+1
      j+=1
    elif ll[tmp[1]][tmp[2]+j]==tmp[0]+1:
      j+=1
    else:
      j=K+1

if l[x2][y2]<0:
  print(-1)
else:
  print(l[x2][y2])
### BUGGY CODE ###

N, M, Q = map(int,input().split())
m =  [[0 for y in range(N+1)] for x in range(N+1)]

for i in range(M):
    l, r = map(int,input().split())
    for j in range(0, l+1):
        for k in range(r,N+1):
            m[j][k]+=1

for i in range(1,Q+1):
    l, r = map(int,input().split())
    print(m[l][r])


### FIXED CODE ###

N, M, Q = map(int,input().split())
m =  [[0 for y in range(N+1)] for x in range(N+1)]
m2 =  [[0 for y in range(N+1)] for x in range(N+1)]
m3 =[[0 for y in range(N+1)] for x in range(N+1)]

for i in range(M):
    l, r = map(int,input().split())
    m[l][r]+=1

for j in range(1, N+1):
    s=0
    for i in range(1, N+1):
        s+=m[i][j]
        m2[i][j]=s

for i in range(1, N+1):
    s=0
    for j in range(i, N+1):
        s+=m2[j][j]-m2[i-1][j]
        m3[i][j]=s

for i in range(1,Q+1):
    l, r = map(int,input().split())
    print(m3[l][r])
### BUGGY CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    max_ans = 10 ** 18
    ans = 0
    for i in A:
        if ans == 0:
            ans = i
        else:
            ans *= i

    if max_ans < ans:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    max_ans = 10 ** 18
    ans = 0
    if 0 in A:
        print(0)
        exit()

    for i, a in enumerate(A):
        if i == 0:
            ans = a
            continue

        ans = ans * a
        if ans > max_ans:
            print(-1)
            exit()

    if max_ans < ans:
        print(-1)
    else:
        print(ans)


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

N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort()
li = [0] * M
for i in range(M):
    B,C= [int(j) for j in input().split()]
    lia = [C,B]
    li[i] = lia
li.sort()
seq = []
for i in range(M):
    lia = [li[i][0] for _ in range(li[i][1])]
    seq += lia
for i in range(min(N,len(seq))):
    k = (i+1)* (-1)
    if A[i] >= seq[k]:
        break
    else:
        A[i] = seq[k]
print(sum(A))

### FIXED CODE ###

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

cb_dict = {}
for _ in range(m):
    b, c = map(int, input().split())
    new = {c:b}
    if c in cb_dict.keys():
        cb_dict[c] += b
    else:
        cb_dict.update(new)

cb_dict = sorted(cb_dict.items(), key=lambda x:x[0], reverse=True)

now_c = 0
now_b = 0
for i in range(n):
    if A[i] >= cb_dict[now_c][0]:
        break
    else:
        A[i] = cb_dict[now_c][0]
        now_b += 1
        if now_b == cb_dict[now_c][1]:
            now_c += 1
            now_b = 0
        if now_c > len(cb_dict)-1:
            break

ans = sum(A)
print(ans)