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

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
mod = 10 ** 9 + 7


def bit(n, k):  # nのkbit目を返す
    return (n >> k) & 1


def bit_count(n):
    return bin(n).count("1")


dp = [0] * (1 << N)
dp[0] = 1

for s in range(1, 1 << N):
    i = bit_count(s)  # i人目の男とのマッチング
    for j in range(N):
        if bit(s, j) and A[i-1][j]:
            dp[s] = (dp[s] + dp[s ^ (1 << j)]) % mod

ans = dp[(1 << N) - 1]
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7


def count_bit_flag(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


def main():
    N = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(N))

    memo = {i: set() for i in range(N)}
    for bit in range(1, 1 << N):
        memo[count_bit_flag(bit)-1].add(bit)

    dp = [0] * (1 << N)
    dp[0] = 1
    for i, bit_list in enumerate(memo.values()):
        for bit in bit_list:
            for j, a in enumerate(A[i]):
                if a and (bit >> j) & 1:
                    dp[bit] += dp[bit ^ (1 << j)]
                    dp[bit] %= mod
    print(dp[(1 << N) - 1])


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

# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
# 列ベクトルとかの受け取り
lists = [int(input()) for _ in range(n)]
ans = []
for i in range(n):
    ans.append(max(lists[:i] + lists[i+1:]))

print(*ans,sep="\n")   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する



### FIXED CODE ###

# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
# 列ベクトルとかの受け取り
lists = [int(input()) for _ in range(n)]
arr = np.array(lists)

maxnum = max(lists)
filter = arr == maxnum
maxarr = arr[filter]
filt2 = arr < maxnum
nextmaxnum = max(arr[filt2]) if len(arr[filt2])!=0 else maxnum

if len(maxarr)>1:
    for _ in range(n):
        print(maxnum)
else:
    for num in arr:
        if num != maxnum:
            print(maxnum)
        else:
            print(nextmaxnum)
### BUGGY CODE ###

a = int(input())
l=list(map(int ,input().split()))
for i in range(a):
    print((l.index(i+1))+1)

### FIXED CODE ###

n=int(input())
l = list(map(int ,input().split()))
out=[0]*n
for i in range(n):
    out[l[i]-1]=i+1
for i in out:
    print(i, end=" ")
### BUGGY CODE ###

from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
lcm = A[0]
MOD = 10**9 + 7
for a in A:
    lcm = (lcm // gcd(lcm,a) * a)
res = 0
for a in A:
    res = (res + lcm // a) % MOD
print(res)
    

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
lcm = A[0]
MOD = 10**9 + 7
for a in A:
    lcm = (lcm // gcd(lcm,a) * a)
res = 0
for a in A:
    res += lcm //a
print(res % MOD)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline


def main():
  N, K = list(map(int, input().split()))
  A = list(map(int, input().split()))

  S = [1]*(N+1)
  for i in range(1, N+1):
    S[i] = S[i-1] * A[i-1]

  pre = S[K]/S[0]
  out = []
  for i in range(K+1, N+1):
    temp = S[i]/S[i-K]
    if pre < temp:
      # print('Yes')
      out.append('Yes')
    else:
      # print('No')
      out.append('No')
    pre = temp

  print(*out, sep='\n')


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


### FIXED CODE ###

from sys import stdin
input = stdin.readline


def main():
  N, K = list(map(int, input().split()))
  A = list(map(int, input().split()))

  # S = [1]*(N+1)
  # for i in range(1, N+1):
  #   S[i] = S[i-1] * A[i-1]

  # pre = S[K]/S[0]
  # out = []
  for i in range(K+1, N+1):
    if A[i-K-1] < A[i-1]:
      print('Yes')
    else:
      print('No')
    # temp = S[i]/S[i-K]
    # if pre < temp:
    #   # print('Yes')
    #   out.append('Yes')
    # else:
    #   # print('No')
    #   out.append('No')
    # pre = temp

  # print(*out, sep='\n')


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

N,M=map(int,input().split())
S,r,s=input(),[],N
exec("N,s,r=(s,max(0,s-M),r+([N-s]if N-s else[]))if S[s]=='0' else(N,s+1,r);"*2*N)
print(*[-1] if s else r[::-1])

### FIXED CODE ###

from collections import deque
INF = 10**18

def append_dq(i, x, dq, dp1):
    while True:
        if not len(dq):
            dq.append(i)
            break
        lxi = dq[-1]
        if x > dp1[lxi]:
            dq.append(i)
            break
        dq.pop()
    return dq
dq = deque()
N,M = map(int, input().split())
S = input().strip()
dp1 = [0] + [INF]*N
dp2 = [-1 for _ in range(N+1)]
dq.append(0)
for i, c in enumerate(S[1:]):
    i+=1
    dq = append_dq(i, dp1[i], dq, dp1)
    idx = dq[0]
    if c != "1" and dp1[idx] != INF:
        dp1[i] = dp1[idx] + 1
        dp2[i] = idx
    if i >= M:
        sxi = dq[0]
        if sxi == (i - M):
            dq.popleft()
if dp1[-1] == INF:
    print(-1)
else:
    r = []
    s = N
    while True:
        if s == 0:
            break
        ns = dp2[s]
        r.append(s-ns)
        s = ns
    print(" ".join(map(str, r[::-1])))
### BUGGY CODE ###

H, W, N = map(int, input().split())
d = 10**9+1
L = []
S = set()
for _ in range(N):
    a, b = map(int, input().split())
    S.add((a, b))
Map =[[0]*5 for _ in range(5)]
ans = [0]*10
for i in S:
    a, b = i
    for i in range(-2, 3):
        for j in range(-2, 3):
            a1, b1 = a+i, b+j

            if (1<=a1<=H) and (1<=b1<=W):
                if (a1, b1) in S:
                    Map[i+2][j+2] = 1
                else:
                    Map[i+2][j+2] = 0
            else:
                Map[i+2][j+2] = -100
    for i in range(-1, 2):
        for j in range(-1, 2):
            res = 0
            for k in range(3):
                for l in range(3):
                    res+=Map[i+1+k][j+1+l]
            if res>=0:
                ans[res]+=1
for i in range(1, 10)[::-1]:
    ans[i] //=i
ans[0] = (W-2)*(H-2)-sum(ans)
for i in ans:
    print(i)

### FIXED CODE ###

H, W, N = map(int, input().split())
d = 10**9+1
L = []
S = set()
for _ in range(N):
    a, b = map(int, input().split())
    S.add((a, b))
Map =[[0]*5 for _ in range(5)]
ans = [0]*10
for i in S:
    a, b = i
    for i in range(-2, 3):
        for j in range(-2, 3):
            a1, b1 = a+i, b+j

            if (1<=a1<=H) and (1<=b1<=W):
                if (a1, b1) in S:
                    Map[i+2][j+2] = 1
                else:
                    Map[i+2][j+2] = 0
            else:
                Map[i+2][j+2] = -100
    for i in range(-1, 2):
        for j in range(-1, 2):
            res = 0
            for k in range(3):
                for l in range(3):
                    res+=Map[i+1+k][j+1+l]
            if res>=0:
                ans[res]+=1
for i in range(1, 10)[::-1]:
    ans[i] //=i
ans[0] = (W-2)*(H-2)-sum(ans)
for i in ans:
    print(i)
### BUGGY CODE ###

n = input()
a = []
n = int(n)

for i in range(n):
    a.append(int(input()))

t = [[a[0]]]

for i in a[1:]:
    flg = 0
    for j, m in enumerate(t):
        if m[-1] < i:
            t[j].append(i)
            flg = 1
            break
    if flg == 0:
        t.append([i])

print(len(t))






### FIXED CODE ###

import bisect

n = int(input())
a = [int(input()) for _ in range(n)]
# それぞれの色の最大値を入れる筒のリスト
t = [a[-1]]

for i in reversed(a[:-1]):
    # それぞれの色のどの値よりも小さかったとき
    idx = bisect.bisect_left(t, i+1)
    # print(i, idx)
    if idx == len(t):
        t.append(i)
    # 効率的な色の探索
    else:
        t[idx] = i
    # print(t)

print(len(t))
### BUGGY CODE ###

S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    if S[i] == "?":
        for d in range(10):
            for k in range(13):
                dp[i+1][(k*10+d)%13] += dp[i][k]
    else:
        d = int(S[i])
        for k in range(13):
            dp[i+1][(k*10+d)%13] += dp[i][k]
print(dp[N][5]%(10**9+7))


### FIXED CODE ###

S = input()
N = len(S)
mod = 10**9+7
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    if S[i] == "?":
        for d in range(10):
            for k in range(13):
                dp[i+1][(k*10+d)%13] = (dp[i+1][(k*10+d)%13]+dp[i][k])%mod
    else:
        d = int(S[i])
        for k in range(13):
            dp[i+1][(k*10+d)%13] = (dp[i+1][(k*10+d)%13]+dp[i][k])%mod
print(dp[N][5]%mod)
### BUGGY CODE ###

import sys
N,Y = map(int,input().split())
ans = '-1 -1 -1'
for i in range(2001):
    for j in range(2001):
        for k in range(2001):
            if 10000*i + 5000*j + 1000*k == Y and i+j+k == N:
                ans = str(i) + ' '+str(j) + ' '+ str(k)
                print(ans)
                sys.exit()
print(ans)

### FIXED CODE ###

import sys
N,Y = map(int,input().split())
ans = '-1 -1 -1'

for i in range(2001):
    for j in range(2001):
        if 10000*i + 5000*j + 1000*(N-i-j) == Y :
            if N-i-j >= 0:
                print(str(i) + ' '+str(j) + ' '+ str(N-i-j))
                sys.exit()
print(ans)
### BUGGY CODE ###

n = int(input())

def digits_of (n): 
    digits = [] 
    while n != 0:
        r = n % 10 
        digits.append(r)
        n = n // 10
    return digits

def is_multiple_of_9 (n): 
    sum = 0
    for i in digits_of (n):
        sum += i
    return sum % 9 == 0 

print('Yes' if is_multiple_of_9(n) else 'No')

### FIXED CODE ###

N = input()
a = [int(n) for n in N]
if int(N) % 9 == 0 and sum(a) % 9 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from heapq import heapify, heappop, heapreplace

n = int(input())
aaa = list(map(int, input().split()))
# print(*(f'{a:08b}' for a in aaa))

all_x = 0
for a in aaa:
    all_x ^= a
mask = ~all_x
bbb = [-(a & mask) for a in aaa if a & mask]
heapify(bbb)

ans = 0
while bbb and bbb[0] < 0:
    a = -heappop(bbb)
    l = a.bit_length()
    while bbb and (-bbb[0]).bit_length() == l:
        x = a ^ (-bbb[0])
        if x:
            heapreplace(bbb, -x)
        else:
            heappop(bbb)
    b = 1 << (l - 1)
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)


### FIXED CODE ###

import numpy as np

n = int(input())
aaa = np.fromiter(map(int, input().split()), np.int64)

all_x = np.bitwise_xor.reduce(aaa)
mask = ~all_x
bbb = aaa & mask

ans = 0
while any(bbb):
    a = bbb.max()
    b = 1 << (int(a).bit_length() - 1)
    bbb[bbb & b > 0] ^= a
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)
### BUGGY CODE ###

n = int(input())
*P, = map(float, input().split())
# DP[i][j]=i枚中j枚が表の確率
DP = [[0 for j in range(n+1)] for i in range(n+1)]
DP[0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        DP[i][j] = DP[i-1][j]*(1-P[i-1])+DP[i-1][j-1]*P[i-1]
print(sum(DP[n][(n+1)//2:]))


### FIXED CODE ###

n = int(input())
*P, = map(float, input().split())
DP = [0 for j in range(n+1)]
DP[0] = 1
for i in range(n):
    DP_ = []
    DP_.append(DP[0]*(1-P[i]))
    for j in range(1, n+1):
        DP_.append(DP[j]*(1-P[i])+DP[j-1]*P[i])
    DP = DP_
print(sum(DP[(n+1)//2:]))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

def solve(S: str):
    dp = [[0] * 4 for _ in range(len(S) + 1)]
    dp[0][0] = 1

    for i, s in enumerate(S):
        for j, a in enumerate('_ABC'):
            dp[i+1][j] = dp[i][j]
            if s == '?':
                dp[i+1][j] = 3 * dp[i][j] + (dp[i][j-1] if 1 <= j else 0)
            if s == a:
                dp[i+1][j] += dp[i][j-1]
    return dp[-1][-1] % MOD


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    result = solve(S)
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

def solve(S: str):
    dp = [[0] * 4 for _ in range(len(S) + 1)]
    dp[0][0] = 1

    for i, s in enumerate(S):
        for j, a in enumerate('_ABC'):
            dp[i+1][j] = dp[i][j]
            if s == '?':
                dp[i+1][j] = 3 * dp[i][j] + (dp[i][j-1] if 1 <= j else 0)
            if s == a:
                dp[i+1][j] += dp[i][j-1]
            dp[i+1][j] %= MOD
    return dp[-1][-1] % MOD


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    result = solve(S)
    print(result)

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

from bisect import bisect_left

n,m = map(lambda x: int(x), input().split())
a = sorted(map(lambda x: int(x),input().split()))

for i in range(m):
    a.insert(bisect_left(a,a[n-1] // 2),a[n-1] // 2)
    a.pop(n)
print(sum(a))


### FIXED CODE ###

import heapq
n,m = map(lambda x: int(x), input().split())
a = list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(a)

for _ in range(m):
    max = heapq.heappop(a)
    heapq.heappush(a,(-1)*(-max//2))
print(-sum(a))
### BUGGY CODE ###

H=int(input())
flag=False
c=0
ans=1
while flag==False:
#for i in range(4):
    H=H//2
    c+=1
    ans+=2**c
    if H==1:
        #break
        flag=True
#print(c)
print(ans)


### FIXED CODE ###

H=int(input())
flag=False
c=0
ans=1
if H==1:
    print(1)
    exit()
while flag==False:
    H=H//2
    c+=1
    ans+=2**c
    if H==1:
        flag=True
print(ans)
### BUGGY CODE ###

N = int(input())
A = tuple(map(int,input().split()))
B = [A.index(i)+1 for i in range(1,N+1)]
print(*B)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [[i+1,A[i]] for i in range(N)]
B.sort(key=lambda x: x[1])
for j in range(N):
  if j == N-1:
    print(B[j][0])
  else:
    print(B[j][0] ,end=" ")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


N, M = map(int, input().split())
mat = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]

ans = N
Q = [set([v for v in range(M)])]
checked = {"".join([str(v) for v in range(M)])}
while Q:
    sports_cand = Q.pop(0)
    n_sports = [0]*M
    for n in range(N):
        for m in range(M):
            if mat[n][m] in sports_cand:
                n_sports[mat[n][m]] += 1
                break
    max_val = max(n_sports)
    for i, v in enumerate(n_sports):
        if v == max_val:
            ans = min(ans, v)
            next_state = "".join(map(str, list(sorted(list(sports_cand-{i})))))
            if len(sports_cand) > 2 and not next_state in checked:
                Q.append(sports_cand-{i})
                checked.add(next_state)
print(ans)


### FIXED CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


N, M = map(int, input().split())
mat = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]

ans = N
Q = [set([v for v in range(M)])]
while Q:
    C = Counter()
    sports_cand = Q.pop(0)
    for n in range(N):
        for m in range(M):
            if mat[n][m] in sports_cand:
                C[mat[n][m]] += 1
                break
    tmp = 0
    for key, val in C.most_common():
        if val > tmp:
            tmp = val
            ans = min(ans, val)
            if len(sports_cand) > 2:
                Q.append(sports_cand-{key})
        else:
            break
print(ans)
### BUGGY CODE ###

# D - Face Produces Unhappiness

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
S = input()
prev_c = None
s_compressed = ""
score = 0
for c in S:
    if c != prev_c:
        s_compressed += c
    else:
        # 初期スコアを出す
        score += 1

    prev_c = c

if len(s_compressed) == 1:
    print(N - 1)
    quit()
else:
    score += 2 * K

print(min((N - 1, score)))


### FIXED CODE ###

# D - Face Produces Unhappiness

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
S = input()

prev_c = None
score = 0
for c in S:
    if c == prev_c:
        score += 1
    prev_c = c

score += 2 * K

print(min((N - 1, score)))
### BUGGY CODE ###

import sys
import heapq
n = int(input())
v_ls = []
for i in range(n):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    v_ls.append((x, y))

already = set()
cur = [(0, 0, 0)]
cost = 0
while len(cur) > 0:
    cur_cost, cur_ind, plus = heapq.heappop(cur)
    cur_x, cur_y = v_ls[cur_ind]
    if cur_ind in already:
        continue
    already.add(cur_ind)
    cost += plus
    for _next, (x, y) in enumerate(v_ls):
        if _next in already:
            continue
        next_cost = min(abs(cur_x - x), abs(cur_y - y))
        heapq.heappush(cur, (cur_cost + next_cost, _next, next_cost))
    if len(already) == n:
        break
print(cost)

### FIXED CODE ###

import sys
N = int(input())
city_ls = list()
for i in range(N):
    city_ls.append([int(i) for i in sys.stdin.readline().split()])
sort_by_x = sorted([[i, j] for i,j in city_ls], key=lambda x:x[0])
G = []
pos2id = {tuple(j) : i for i, j in enumerate(city_ls)}
for i in range(len(sort_by_x)-1):
    current_by_x = sort_by_x[i]
    next_by_x = sort_by_x[i + 1]
    G.append((abs(current_by_x[0] - next_by_x[0]),current_by_x, next_by_x))
sort_by_x.sort(key=lambda x:x[1])
for i in range(len(sort_by_x) - 1):
    current_by_x = sort_by_x[i]
    next_by_x = sort_by_x[i + 1]
    G.append((abs(current_by_x[1] - next_by_x[1]), current_by_x, next_by_x))
G.sort(key=lambda x:x[0])
sum_cost = 0
par = [i for i in range(N)]
rank = [1 for i in range(N)]
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        pass
    else:
        if rank[x] > rank[y]:
            par[y] = x
            rank[x] += rank[y]
        else:
            par[x] = par[y]
            rank[y] += rank[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

for i in G:
    (cost, _from, _to) = i
    _from = pos2id[tuple(_from)]
    _to = pos2id[tuple(_to)]
    if is_same(_from, _to):
        continue
    unite(_from, _to)
    sum_cost += cost
print(sum_cost)
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict
from bisect import bisect_right

s = ns()
t = ns()

ok = True

sset = set(list(s))
for ti in t:
    if ti not in sset:
        ok = False
        break

if not ok:
    print(-1)

else:
    n = len(s)

    charidx = defaultdict(list)

    for i, si in enumerate(s):
        charidx[si].append(i)
    for i, si in enumerate(s):
        charidx[si].append(n+i)

    ks = charidx.keys()

    move = [{ki: -1 for ki in ks} for _ in range(n)]

    for i, si in enumerate(s):
        for ki in ks:
            nexidx = bisect_right(charidx[ki], i)
            move[i][ki] = (charidx[ki][nexidx] - i) % (n+1)

    cur = s.index(t[:1])
    ans = cur
    for ti in t[1:]:
        nex = move[cur][ti]
        ans += nex
        cur = (cur + nex) % n

    print(ans+1)



### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict
from bisect import bisect_right

s = ns()
t = ns()

ok = True

sset = set(list(s))
for ti in t:
    if ti not in sset:
        ok = False
        break

if not ok:
    print(-1)

else:
    n = len(s)

    charidx = defaultdict(list)

    for i, si in enumerate(s):
        charidx[si].append(i)
    for i, si in enumerate(s):
        charidx[si].append(n+i)

    ks = charidx.keys()

    move = [{ki: -1 for ki in ks} for _ in range(n)]

    for i, si in enumerate(s):
        for ki in ks:
            idxlist = charidx[ki]
            nexidx = bisect_right(idxlist, i)
            move[i][ki] = (idxlist[nexidx] - i) % (n+1)

    cur = s.index(t[:1])
    ans = cur
    for ti in t[1:]:
        nex = move[cur][ti]
        ans += nex
        cur = (cur + nex) % n

    print(ans+1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [None] + a

ans = set()
cnt = [0] * (n + 1)

for i in range(n, 0, -1):
    if cnt[i] % 2 != a[i] % 2:
        ans.add(i)

        st = set()
        j = 1
        while j * j <= i:
            if i % j == 0:
                st.add(j)
                st.add(i // j)
            j += 1
        for d in st:
            cnt[d] += 1

print(len(ans))
print(*ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
a = [None] + a
a = tuple(a)

ans = set()
cnt = [0] * (n + 1)

for i in range(n, 0, -1):
    if cnt[i] % 2 != a[i] % 2:
        ans.add(i)

        st = set()
        j = 1
        while j * j <= i:
            if i % j == 0:
                st.add(j)
                st.add(i // j)
            j += 1
        for d in st:
            cnt[d] += 1

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

s = input()
t = input()
ls = len(s)
lt = len(t)
sl = [0]*(ls+1)
tl = [0]*(lt+1)
def g(x):
  if x == "A":
    return 1
  else:
    return 2
for i in range(ls):
  sl[i+1] = sl[i] + g(s[i])
for i in range(lt):
  tl[i+1] = tl[i] + g(t[i])
for _ in range(int(input())):
  a,b,c,d = map(int, input().split())
  if (sl[b]-tl[d]-sl[a-1]+tl[c-1])%3 == 0:
    print("YES")
  else:
    print("NO")
  

### FIXED CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)
sl = [0]*(ls+1)
tl = [0]*(lt+1)
for i in range(ls):
  if s[i] == "A":
    sl[i+1] = sl[i] + 1
  else:
    sl[i+1] = sl[i] + 2
for i in range(lt):
  if t[i] == "A":
    tl[i+1] = tl[i] + 1
  else:
    tl[i+1] = tl[i] + 2
for _ in range(int(input())):
  a,b,c,d = map(int, input().split())
  if (sl[b]-tl[d]-sl[a-1]+tl[c-1])%3 == 0:
    print("YES")
  else:
    print("NO")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    if ans != -1:
        ans *= a[i]
    elif a[i] == 0:
        ans = 0
        break
    if ans > 10**18:
        ans = -1
print(ans)