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

MOD = 998244353


def encode(num, total, S):
    return num * (S+1) + total


def decode(val, S):
    return val // (S+1), val % (S+1)


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split()), reverse=True))
    prev = {encode(0, 0, S): 1}
    for i in range(N):
        cur = {k: prev[k] for k in prev}
        for prevkey in prev:
            num, total = decode(prevkey, S)
            if total + A[i] > S:
                continue
            key = encode(num+1, total + A[i], S)
            if key in cur:
                cur[key] = cur[key] + prev[prevkey]
            else:
                cur[key] = prev[prevkey]
        prev = cur
    ans = 0
    for num in range(1, N+1):
        key = encode(num, S, S)
        if key in cur:
            ans = (ans + cur[key] * pow(2, N-num, MOD)) % MOD
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split())))
    prev = [0] * (S+1)
    prev[0] = pow(2, N, MOD)
    half = pow(2, MOD-2, MOD) % MOD
    for i in range(N):
        cur = list(prev)
        for total in range(S+1):
            if total + A[i] > S:
                continue
#            key = encode(num+1, total + A[i], S)
            cur[total + A[i]] = (cur[total + A[i]] +
                                 prev[total] * half) % MOD
        prev = cur
    print(cur[S])


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

s = input()
k = int(input())

ans = set()
for i in range(len(s)+1):
    for j in range(i + 1, len(s)+1):
        ans.add(s[i:j])

# print(ans)
print(sorted(list(ans))[k-1])

### FIXED CODE ###

s = input()
k = int(input())

ans = set()
for i in range(len(s)):
    for j in range(1, k+1):
        ans.add(s[i:i+j])

# print(ans)
print(sorted(list(ans))[k-1])
### BUGGY CODE ###

def main():
    A = input()[::-1]
    A = "0" + A
    # lis_num = [int(s) for s in A]

    # print(lis_num)

    # S = [0] * len(lis_num)
    S = [0] * len(A)
    cnt = [0] * 2019
    cnt[0] = 1

    for i in range(len(A) - 1):
        S[i + 1] = S[i] + int(A[i + 1]) * pow(10, i)
        cnt[S[i + 1] % 2019] += 1

    # print(S)


    # for i in S:
    #     cnt[i % 2019] += 1

    ans = 0

    for i in range(2019):
        ans += cnt[i] * (cnt[i] - 1) // 2

    print(ans)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    A = input()[::-1]
    A = "0" + A
    # lis_num = [int(s) for s in A]

    # print(lis_num)

    # S = [0] * len(lis_num)
    S = [0] * len(A)
    cnt = [0] * 2019
    cnt[0] = 1

    for i in range(len(A) - 1):
        S[i + 1] = (S[i] + int(A[i + 1]) * pow(10, i, 2019)) % 2019
        cnt[S[i + 1] % 2019] += 1

    # print(S)

    # for i in S:
    #     cnt[i % 2019] += 1

    ans = 0

    for i in cnt:
        ans += i * (i - 1) // 2

    print(ans)


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

from functools import reduce
from sys import stdin
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

if __name__ == "__main__":
    mod = 10**9+7
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]
    ans = 0
    l = reduce(lcm,A)
    for j in A:
        ans += (l//j)
        ans %= mod
    print(ans)

### FIXED CODE ###

from sys import stdin
import fractions
mod = 10**9+7
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
ans = 0
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, pow(b, mod-2,mod))

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

l = 1
for i in A:
    l = lcm(l,i)
    
for j in A:
    ans += div(l,j)
    ans %= mod
    
print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input().replace("AC","aC")

for i in range(q):
    l,r = map(int,input().split())
    print(s[l-1:r-1].count("a"))

### FIXED CODE ###

n,q = map(int,input().split())
s = input().replace("AC","aC")
L = [0]*n
cnt = 0
for i in range(1,n):
    if s[i-1] == "a":
        cnt += 1
    L[i]=cnt
        
for i in range(q):
    l,r = map(int,input().split())
    print(L[r-1] - L[l-1])
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
s = 0
def count(A, n):
    for i in range(n):
        if (A[i] % 2 == 1) or (A[i] == 0):
            break
        A[i] = A[i] // 2
    return True

while True:
    if count(A, n):
        s += 1
    else:
        break
    
print(s)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
s = 0

def count(A, n):
    for i in range(n):
        if (A[i] % 2 == 1) or (A[i] == 0):
            return False
        A[i] = A[i] // 2
    return True

while True:
    if count(A, n):
        s += 1
    else:
        break
    
print(s)
### BUGGY CODE ###

n, m = map(int, input().split())
if abs(n-m) > 1:
	print(0)
	exit()
i_n = n
i_m = m
np = 1
mp = 1
while True:
	np = np * i_n
	mp = mp * i_m
	i_n -= 1
	i_m -= 1
	if i_n < 1:
		i_n = 1
	if i_m < 1:
		i_m = 1
	if i_n == 1 and i_m == 1:
		break
s = 2 if n == m else 1
r = (mp*np*s) % (10**9 + 7)
print(r)

### FIXED CODE ###

import math

n, m = map(int, input().split())
if abs(n-m) > 1:
	print(0)
	exit()
s = 2 if n == m else 1
np = math.factorial(n)
mp = math.factorial(m)
r = (mp*np*s) % (10**9 + 7)
print(r)
### BUGGY CODE ###


def gcd(a,b):
    if a < b:
        a, b = b, a
    if mem[a][b]:
        return mem[a][b]
    if b == 0:
        return a
    mem[a][b] = gcd(b, a % b)
        
    return mem[a][b]

k = int(input())
ans = 0
mem = [[0 for a in range(k+1)]for b in range(k+1)]
n = k+1
for i in range(1,n):
    for j in range(1,n):
        for k in range(1,n):
            ans += gcd(gcd(i,j),k)
print(ans)


### FIXED CODE ###

def gcd(a,b):
    if a < b:
        a, b = b, a
    if mem[a][b]:
        return mem[a][b]
    if b == 0:
        return a
    mem[a][b] = gcd(b, a % b)
    return mem[a][b]

k = int(input())
ans = 0
mem = [[0 for a in range(k+1)]for b in range(k+1)]
n = k+1
for i in range(1,n):
    for j in range(1,n):
        d = gcd(i,j)
        for k in range(1,n):
            ans += gcd(d,k)
print(ans)
### BUGGY CODE ###

from numpy import*
n,a=open(0)
n=int(n)
a=cumsum(int64([0]+a.split()))
dp=zeros((n,n+1),'i8')
for k in range(1,n):
  l=arange(n-k)
  r=arange(k+1,n+1)
  m=array([arange(i+1,j)for i,j in zip(l,r)]).T
  dp[l,r]=amin(dp[l,m]+dp[m,r],0)+a[r]-a[l]
print(dp[0,n])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def main():
  def s(l,r):
    k=l*n+r
    if d[k]:return d[k]
    if r-l<2:return 0
    d[k]=t=min(s(l,i)+s(i,r)for i in range(l+1,r))+a[r-1]-a[l-1]
    return t
  n,*a=map(int,open(0).read().split())
  d=[None]*(n*n+1)
  for i in range(n-1):a[i+1]+=a[i]
  a+=[0]
  print(s(0,n))
main()
### BUGGY CODE ###

a, b = map(int,input().split())

f = [0] * 2
for i in range(a, b + 1):
    if i == 0:
        f[0] += 1
        break
    elif i < 0:
        f[1] += 1

if f[0] > 0:
    print("Zero")
elif f[1] % 2 == 1:
    print("Negative")
else:
    print("Positive")

### FIXED CODE ###

a, b = map(int,input().split())

if a <= 0 and 0 <= b:
    print("Zero")
    exit()

if a > 0:
    print("Positive")
    exit()

if (b - a) % 2 == 0:
    print("Negative")
else:
    print("Positive")
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
res = 0
for i in range(N-1):
    for j in range(i+1, N):
        res = (res + A[i]*A[j]) % (10**9+7)
print(res)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [0]*N
res = 0
B[N-1] = A[N-1]
for i in range(1, N):
    B[N-i-1] = B[N-i] + A[N-i-1]
for i in range(N-1):
    res = (res + A[i] * B[i+1]) % (10**9+7)
print(res)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
l = [0]*n
ans = 0

for i in range(n):
    l[i] = i + 1 + a[i]
    ans += l[:i].count(i + 1 - a[i])


print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}
ans = 0

for i in range(n):
    l = i + a[i]
    r = i - a[i]
    if l not in d:
        d[l] = 1
    else:
        d[l] += 1
    if r in d:
        ans += d[r]

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

import math

n = int(input())
l = list(map(int, input().split()))
ans = 0
l.sort()

for i in range(n-2):
    for j in range(i+1, n-1):
        buf = l[i]+l[j]
        Min = j+1
        Max = n
        while(Min!=Max):
            Mid = math.floor((Min+Max)/2)
            if l[Mid] < buf:
                Min = Mid+1
            else:
                Max = Mid
        ans += Min-(j+1)
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
ans = 0
l.sort()

for i in range(n-2):
    for j in range(i+1, n-1):
        c_i = bisect.bisect_left(l, l[i]+l[j])
        if c_i > j:
            ans += c_i - j - 1
        else:
            continue
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
cnt = defaultdict(int)
for a in A:
    cnt[a] += 1
n = 1
m = max(A)
while n <= 2 * m:
    n *= 2
n //= 2
ans = 0
while n > 0:
    for a in A:
        if cnt[a] == 0:
            continue
        b = n - a
        c = 0
        if b == a and cnt[a] > 1:
            c = cnt[a] // 2
        elif b != a and cnt[b] > 0:
            c = min(cnt[a], cnt[b])
        cnt[a] -= c
        cnt[b] -= c
        ans += c
    n //= 2
print(ans)

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
cnt = defaultdict(int)
for a in A:
    cnt[a] += 1
n = 1
while n <= 2 * A[0]:
    n *= 2
n //= 2
ans = 0
while n > 0:
    for a in A:
        if cnt[a] == 0:
            continue
        b = n - a
        if b < 0:
            continue
        if b > a:
            break
        c = 0
        if b == a and cnt[a] > 1:
            c = cnt[a] // 2
        elif b != a and cnt[b] > 0:
            c = min(cnt[a], cnt[b])
        cnt[a] -= c
        cnt[b] -= c
        ans += c
    n //= 2
print(ans)
### BUGGY CODE ###

N = int(input())

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

Q = int(input())

BC = [map(int, input().split()) for _ in range(Q)]
B, C = [list(i) for i in zip(*BC)]

list = [0] * 100001
sum = 0
for i in range(100001):
    list[i] = A.count(i)

for i in range(len(A)):
    sum += A[i] 

for i in range(Q):
    sum = list[B[i]] * (C[i] -B[i]) + sum
    list[C[i]] = list[C[i]] + list[B[i]]
    list[B[i]] = 0
    print(sum)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B=[]
C=[]

for _ in range(Q):
    bi, ci = list(map(int, input().split()))
    B.append(bi)
    C.append(ci)

dic = {}
for i in A:
    dic[i] = dic.get(i,0) + 1

sum = sum(A)

for i in range(Q):
    sum += dic.get(B[i], 0) * (C[i] -B[i])
    dic[C[i]] = dic.get(C[i], 0) + dic.get(B[i], 0)
    dic[B[i]] = dic.get(B[i], 0)
    dic[B[i]] = 0
    print(sum)
### BUGGY CODE ###

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

MOD = 10**9 + 7

ans = 0
two_factor = 1
for d in range(60):
    n0 = 0
    n1 = 0
    for i in range(N):
        if A[i] & (1<<d):
            n1 += 1
        else:
            n0 += 1
    tmp = (1<<d) % MOD
    n = n0 * n1 % MOD
    tmp = tmp * n % MOD
    ans = (ans + tmp) % MOD

print(ans)


### FIXED CODE ###

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

mod = 10**9 + 7

ans = 0
for i in range(60):
    X = sum([1 for x in A if (x >> i) & 1])
    ans += (1 << i) * X * (N - X)
    ans %= mod

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

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

count = 0
for i in range(0,N,1):
    for j in range(i+1,N,1):
        if S[i] == S[j]:
            continue
        for k in range(j+1,N,1):
            if S[j] != S[k] and S[i] != S[k] and abs(k-j) != abs(j-i):
                count +=1

print(count)


### FIXED CODE ###

N = int(input())
S =input()
r = S.count('R')
b = S.count('B')
g = S.count('G')
x = r*b*g

count = 0
for i in range(0,N,1):
    for j in range(i+1,N,1):
        if 2*j-i > len(S)-1:
            continue
        if S[i] != S[j] and S[j] != S[2*j-i] and S[i] != S[2*j-i]:
            count +=1

print(x-count)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i,j in enumerate(a):
    cnt1,cnt2=1,1
    for k in range(i-1,-1,-1):
        if a[k]>j:
            cnt1+=1
        else:
            break
    for k in range(i+1,n):
        if a[k]>j:
            cnt2+=1
        else:
            break
    ans+=cnt1*cnt2*j
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(list(enumerate(a)),key=lambda x:x[1])

l=1
while l<2*(n+2)-1:
	l*=2
l-=1
seg=[True]*l
seg[0]=False

def update(i):
	if seg[i]:
		seg[i]=False
		update((i-1)//2)

update((l-1)//2)
update((l-1)//2+n+1)

def search_left(i,j):
	if j==1:
		if i%2==1:
			return search_left((i-1)//2,1)
		else:
			if seg[i-1]:
				return search_left((i-1)//2,1)
			else:
				return search_left(i-1,0)
	else:
		if i<l//2:
			return search_left(2*i+2-seg[2*i+2],0)
		else:
			return i

def search_right(i,j):
	if j==1:
		if i%2==0:
			return search_right((i-1)//2,1)
		else:
			if seg[i+1]:
				return search_right((i-1)//2,1)
			else:
				return search_right(i+1,0)
	else:
		if i<l//2:
			return search_right(2*i+1+seg[2*i+1],0)
		else:
			return i

ans=0
for i,j in a:
	s=(l//2+1+i)
	p=search_left(s,1)
	q=search_right(s,1)
	ans+=(s-p)*(q-s)*j
	update(s)

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

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]

neigh = {}

for i in range(n - 1) :
    neigh.setdefault(ab[i][0], []).append(ab[i][1])

sortKey = sorted(neigh.keys(), reverse=True)

for i in range(len(sortKey)) :
    for j in range(i + i, len(sortKey)) :
        if sortKey[i] in neigh[sortKey[j]] :
            neigh[sortKey[j]] += neigh[sortKey[i]]

ans = [0] * n
#print(neigh)
#print(neigh)

for i in range(q) :
    if px[i][0] in neigh :
        for e in neigh[px[i][0]] :
            ans[e - 1] += px[i][1]
    ans[px[i][0] - 1] += px[i][1]

print(*ans)


### FIXED CODE ###

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]

neigh = {}

ans = [0] * n
#print(neigh)
#print(neigh)

for i in range(q) :
    ans[px[i][0] - 1] += px[i][1]

for i in range(n - 1) :
    neigh.setdefault(ab[i][0], []).append(ab[i][1])

sortKey = sorted(neigh.keys())

for k in sortKey :
    for e in neigh[k] :
        ans[e - 1] += ans[k - 1]

print(*ans)

'''
    ans[sortKey]

for i in range(len(sortKey)) :
    for j in range(i + i, len(sortKey)) :
        if sortKey[i] in neigh[sortKey[j]] :
            neigh[sortKey[j]] += neigh[sortKey[i]]
            break

    if px[i][0] in neigh :
        for e in neigh[px[i][0]] :
            ans[e - 1] += px[i][1]


print(*ans)
'''
### BUGGY CODE ###

N=int(input())

listA=[]

try:
    listA = list(input().split())
    #listA<-[1,2,2,3,1]
    #print(listA)
    #ここに逐次処理を書けばいいと思う。
except:
    quit();
    #または、quit(),os.exit()をして止める。


for i in listA:
    if listA.count(i) >= 2:
        print('NO')
        quit();

print('YES')

### FIXED CODE ###

N=int(input())

listA=[]

try:
    listA = list(input().split())
    #listA<-[1,2,2,3,1]
    #print(listA)
    #ここに逐次処理を書けばいいと思う。
except:
    quit();
    #または、quit(),os.exit()をして止める。


listA.sort()


for i in range(len(listA)-1):
    if listA[i] == listA[i+1]:
        print('NO')
        quit();

print('YES')
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
p = LF()

dp = [[0.0]*(N+1) for i in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(N):
        dp[i+1][j+1] += dp[i][j]*p[i]
        dp[i+1][j] += dp[i][j]*(1-p[i])

print(sum(dp[N][N//2+1:]))

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
p = LF()

dp = [[0.0]*(N+1) for i in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(N):
        dp[i+1][j+1] += dp[i][j]*p[i]
        dp[i+1][j] += dp[i][j]*(1-p[i])

print(sum(dp[N][N//2+1:]))
### BUGGY CODE ###

S = [int(e) for e in input().split()]
# S = list(map(int, input().replace(' ', '')))
list_a =  [int(e) for e in input().split()]
# list_a = list(map(int, input().replace(' ', '')))
list_b =  [int(e) for e in input().split()]
# list_b = list(map(int, input().replace(' ', '')))

dis_list = []

for i in range(S[2]):
    dis_list.append([int(e) for e in input().split()])

cost_list = []

for i in list_a:
    for j in list_b:
        cost_list.append(i+j)

for l in dis_list:
    cost_list.append(cost_list[S[0]*(l[0]-1)+l[1]-1] - l[2])

print(min(cost_list))
# print('cost_list:',cost_list)
# print('list_a:',list_a)
# print('list_b:',list_b)

### FIXED CODE ###

S = [int(e) for e in input().split()]
list_a =  [int(e) for e in input().split()]
list_b =  [int(e) for e in input().split()]

dis_list = []

for i in range(S[2]):
    dis_list.append([int(e) for e in input().split()])

min_num1 = min(list_a) + min(list_b)

min_num2_list = []

for l in dis_list:
    min_num2_list.append(list_a[l[0]-1] + list_b[l[1]-1] - l[2])

min_num2 = min(min_num2_list)

if min_num1 > min_num2:
    print(min_num2)
else:
    print(min_num1)
### BUGGY CODE ###

from math import sqrt, ceil

cache = set()
primes = {2}
def isprime(n):
    if n in primes:
        return True
    for i in range(3, ceil(sqrt(n))+1, 2):
        if n % i == 0:
            return False
    primes.add(n)
    return True

def solve(l, r):
    cnt = 0
    if l <= 3 <= r:
        cnt = 1
        l = 5
    if l % 4 == 3:
        l += 2
    for n in range(l, r+1, 4):
        if n in cache:
            cnt += 1
            continue
        m = (n - 1) // 2
        assert n % 4 == 1
        if isprime(m+1) and isprime(n):
            cache.add(n)
            cnt += 1
    return cnt

def main():
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(solve(l, r))

def check(l, r):
    print((l,r), solve(l,r))
"""
check(3, 7)
check(13, 13)
check(7, 11)
check(1, 11)
check(2017, 2017)
check(1, 53)
check(13, 91)
check(1, 10**5-1)
"""
main()


### FIXED CODE ###

from math import sqrt, ceil

cache = {3}
primes = {2,3}
def isprime(n):
    if n in primes:
        return True
    for i in range(3, ceil(sqrt(n))+1, 2):
        if n % i == 0:
            return False
    primes.add(n)
    return True

def prepare():
    l = 5
    r = 10**5-1
    for n in range(l, r+1, 4):
        if n in cache:
            continue
        m = (n - 1) // 2
        if isprime(m+1) and isprime(n):
            cache.add(n)

def solve(l, r):
    cnt = 0
    if l <= 3 <= r:
        cnt = 1
        l = 5
    if l % 4 == 3:
        l += 2
    for n in range(l, r+1, 4):
        if n in cache:
            cnt += 1
            continue
        m = (n - 1) // 2
        assert n % 4 == 1
        if isprime(m+1) and isprime(n):
            cache.add(n)
            cnt += 1
    return cnt

def main():
    global cache
    from bisect import bisect_left, bisect_right
    cache = sorted(cache)
    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        i = bisect_left(cache, l)
        j = bisect_right(cache, r)
        print(j-i)

prepare()
main()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
t = 0
ans = 0
u =[0]*n
d =[0]*n
for i in range(n):
    for j in range(n):
        if b[i]>a[j]:
            t+=1
    u[i]=t
    t=0
for i in range(n):
    for j in range(n):
        if b[i]<c[j]:
            t+=1
    d[i]=t
    t=0
for i in range(n):
    ans+=u[i]*d[i]
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
t = 0
ans = 0
u =[0]*n
d =[0]*n
a2 =[]
b2 =[]
c2 =[]

for i in range(n):
    a2.append([2,a[i]])
for i in range(n):
    b2.append([1,b[i]])
for i in range(n):
    c2.append([0,c[i]])
a2b2=a2+b2
b2c2=b2+c2

a2b2.sort(key = lambda x:(x[1],x[0]))
b2c2.sort(key = lambda x:(x[1],x[0]),reverse=True)

j=0
c=0
for i in range(2*n):
    if a2b2[i][0]==2:
        c+=1
    if a2b2[i][0]==1:
        u[j]=c
        j+=1
j=0
c=0
for i in range(2*n):
    if b2c2[i][0]==0:
        c+=1
    if b2c2[i][0]==1:
        d[j]=c
        j+=1
d.reverse()
for i in range(n):
    ans+=u[i]*d[i]
print(ans)
### BUGGY CODE ###

n = int(input())
A = map(int, input().split())
out = 1
for a in A:
    out *= a
out = -1 if (out > 10 ** 18) else out
print(out)


### FIXED CODE ###

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

if 0 in A:
    print(0)
else:
    out = 1
    for a in A:
        out *= a
        if out > 10 ** 18:
            out = -1
            break
    print(out)