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

n,k=map(int,input().split())
s=input()
ans=0

if k==2 or k==5:
    for i,p in enumerate(s):
        p=int(p)
        if p%k==0:
            ans+=i+1

else:
    inv10=pow(10,k-2,k)
    inv=10
    total=0
    S=[0]*k
    S[0]=1
    for i,p in enumerate(s):
        inv*=inv10
        p=int(p)
        total+=p*inv
        S[total%k]+=1
    for i in S:
        ans+=i*(i-1)//2

print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
s=map(int,list(input()))
ans=0
if k==2 or k==5:
    for i,p in enumerate(s):
        if p%k==0:
            ans+=i+1
else:
    inv10=pow(10,k-2,k)
    inv=10
    total=0
    S=[0]*k
    S[0]=1
    for i,p in enumerate(s):
        inv*=inv10
        inv%=k
        total+=p*inv
        total%=k
        ans+=S[total]
        S[total]+=1
print(ans)
### BUGGY CODE ###

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


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
sum=1
check=0
a.sort()

for i in range(n):
    x=a[i]
    if x==0:
        print(0)
        exit()
    if not check==-1:
        sum*=x
        if sum>10**18:
            check=-1
if check==-1:
        print(-1) 
        exit()  
print(sum)
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
G=[["#"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["#"]+list(input())+["#"]
X=deque()
Y=deque()
V=[[0]*(w+2) for i in range(h+2)]
V[0]=[0]*(w+2)
for i in range(1,h+1):
  V[i]=[0]+[10**7]*w+[0]
V[h+1]=[0]*(w+2)
for i in range(1,h+1):
  for j in range(1,w+1):
    if G[i][j]=="#":
      X.append(i)
      Y.append(j)
      V[i][j]=0
XX=[-1,0,0,1]
YY=[0,-1,1,0]
while len(X)!=0:
  x=X[0]
  y=Y[0]
  X.popleft()
  Y.popleft()
  for i in range(4):
    if V[x+XX[i]][y+YY[i]]==10**7:
      V[x+XX[i]][y+YY[i]]=V[x][y]+1
      X.append(x+XX[i])
      Y.append(y+YY[i])
ans=0
for i in range(h+2):
  for j in range(w+2):
    if V[i][j]>ans:
      ans=V[i][j]
print(ans)

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
G=[["#"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["#"]+list(input())+["#"]
X=deque()
Y=deque()
V=[[0]*(w+2) for i in range(h+2)]
V[0]=[0]*(w+2)
for i in range(1,h+1):
  V[i]=[0]+[10**7]*w+[0]
V[h+1]=[0]*(w+2)
for i in range(1,h+1):
  for j in range(1,w+1):
    if G[i][j]=="#":
      X.append(i)
      Y.append(j)
      V[i][j]=0
XX=[-1,0,0,1]
YY=[0,-1,1,0]
while len(X)!=0:
  x=X[0]
  y=Y[0]
  X.popleft()
  Y.popleft()
  for i in range(4):
    if V[x+XX[i]][y+YY[i]]==10**7:
      V[x+XX[i]][y+YY[i]]=V[x][y]+1
      X.append(x+XX[i])
      Y.append(y+YY[i])
ans=0
for i in range(h+2):
  for j in range(w+2):
    if V[i][j]>ans:
      ans=V[i][j]
print(ans)
### BUGGY CODE ###

import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    L = [0] * Q
    R = [0] * Q
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[i]], i, -1))
            D[C[i]] = i

    for i in range(Q):
        l, r = map(int, input().split())
        L[i] = l
        R[i] = r
        E.append((l - 1, r - 1, i))

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    ANS = [0] * Q
    y_list = []
    for e in E:
        if e[2] == -1:
            y_list.append(e[1])
            y_list.sort()
        else:
            ans = bisect.bisect_right(y_list, e[1])
            ANS[e[2]] = e[1] - e[0] + 1 - ans

    for i in range(Q):
        print(ANS[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

a,b,c,k = map(int, input().split())
ans = 0
for i in range(k):
    if a > 0:
        ans +=1
        a -=1
    elif b >0:
        b -=1
    else:
        ans -= 1
        c -=1

print(ans)


### FIXED CODE ###

a,b,c,k = map(int, input().split())
ans = 0

if a >= k:
    ans += k
    print(ans)
    k -=a
else:
    ans += a
    k -= a

if k >0:
    if b >= k:
        print(ans)
        k -=b
    else:
        k -=b

if k > 0:
    if c >= k:
        ans -=k
        print(ans)
        k -=c
    else:
        k -=c
        print(ans)
### BUGGY CODE ###

n = int(input())
numlist = [int(_) for _ in input().split()]
setnum = set(numlist)
dicnum = {}

for i in setnum:
    dicnum[i] = numlist.count(i)
    
for j in range(n):
    ans = 0
    dicpos = numlist[j]
    for k in setnum:
        if k == dicpos:
            cal = dicnum[k] - 1
        else:
            cal = dicnum[k]
        if cal >= 2:
            ans += cal*(cal-1)//2
    print(ans)

### FIXED CODE ###

n = int(input())
numlist = [int(_) for _ in input().split()]
numdic = {}
nsum = 0

for i in range(n):
    if numlist[i] in numdic:
        numdic[numlist[i]] += 1
    else:
        numdic[numlist[i]] = 1

for k in numdic:
    nsum += numdic[k] * (numdic[k] - 1) // 2

for j in range(n):
    ans = nsum
    cal = numdic[numlist[j]]
    if cal >= 2:
        ans = ans - (cal-1)
    print(ans)
### BUGGY CODE ###

import sys
import heapq

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)

BC = [list(map(int, input().split())) for _ in range(m)]
for card_set in BC:
    for i in range(card_set[0]):
        heapq.heappushpop(A, card_set[1])

print(sum(A))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

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

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

for i in range(N - K):
  list_a = list(A[i:i+K])
  list_b = list(A[i+1:i+K+1])
  if list_a[0] < list_b[-1]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N, K = list(map(int,input().split()))
 
A = list(map(int,input().split()))
 
for i in range(N - K):
  if A[i] < A[i + K]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import copy

N = int(input())
A = []
for i in range(N):
    A.append( [ int(n) for n in input().split() ] )

empty = [ [] for i in range(N) ]
default = [0 for i in range(N)]
day = 0
while(True):
    day += 1
    v = copy.deepcopy(default)
    for p in range(N):
        if len(A[p]) == 0:
            continue
        q = A[p][0]-1
        if v[p] == 0  and  v[q] == 0  and  A[q][0]-1 == p:
            v[p] = 1
            v[q] = 1
            del A[p][0]
            del A[q][0]
        
    if A == empty:
        print(day)
        break
    
    if v == default:
        print(-1)
        break


### FIXED CODE ###

# match of  a vs b
def match(a, b):
    """
    :type a: int
    :type b: int
    :rtype: int
    """
    return min(a,b) + N * max(a,b)

N = int(input())
A = []
for i in range(N):
    A.append( [ int(n)-1 for n in input().split() ] )

# NEXT[ match(a,b) ]  must be held after  match(a,b)
NEXT = [ [] for i in range(N*N) ]
# How many matches must be held before  match(a,b)
before = [ 0 for i in range(N*N) ]

for i in range(N):
    for j in range(N-2):
        # i vs A[i][j+1]  must be held after  i vs A[i][j]
        NEXT[ match(i,A[i][j]) ].append( match(i,A[i][j+1]) )
        before[ match(i,A[i][j+1]) ] += 1
        
q  = []
q0 = []

for i in range(N):
    for j in range(i+1,N):
        if before[ match(i,j) ] == 0:
            q.append( match(i,j) )
            
day = 0

while True:
    day += 1
    for M in q:
        for m in NEXT[M]:
            before[m] -= 1
            if before[m] == 0:
                q0.append(m)
        NEXT[M] = []
    q = q0
    q0 = []
    #print(NEXT)
    #print(before)
    if q == []:
        break

if NEXT == [ [] for i in range(N*N) ]:
    print(day)
else:
    print(-1)
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
for i in range(n-1):
    for j in range(i+1,n):
        if h[i]-1>h[j]:
            print('No')
            exit()
print('Yes')

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
k=h[0]-1
for i in range(1,n-1):
    if k<=h[i]-1:k=h[i]-1
    if k>h[i+1]:
        print('No')
        exit()
print('Yes')
### BUGGY CODE ###

import numpy as np


n, m = [int(x) for x in input().split()]

INF = int(10e8 + 1)
dp = np.full(1 << n, INF, dtype=int)
dp[0] = 0

for j in range(m):
    cost = int(input().split()[0])

    boxes = [int(x)-1 for x in input().split()]
    mask = 0

    for box in boxes:
        mask |= 1 << box
    
    for i in range(1 << n):
        dp[i | mask] = min(
                dp[i | mask],
                dp[i] + cost
            )

res = dp[-1] if dp[-1] != INF else -1
print(res)


### FIXED CODE ###

n, m = [int(x) for x in input().split()]

INF = int(10e8 + 1)
dp = [INF] * (1 << n)
dp[0] = 0

for j in range(m):
    cost = int(input().split()[0])

    boxes = [int(x)-1 for x in input().split()]
    mask = 0

    mask = sum(1 << box for box in boxes)
    
    for i in range(1 << n):
        if dp[i] + cost < dp[i | mask]:
            dp[i | mask] = dp[i] + cost

res = dp[-1] if dp[-1] != INF else -1
print(res)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
MOD=10**9+7
n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

dp = [[0]*(2**n) for i in range(n+1)]
dp[0][0] = 1
for m in range(1,n+1):
    for a in range(2**n):
        if bin(a).count("1") != m: continue
        dp[m][a] = sum(dp[m-1][a-2**c] for c in range(n) if 2**c&a != 0 and A[m-1][c]==1)%MOD


print(dp[n][2**n-1])

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

def itercomb(n,k):
    _a = (1<<k)-1
    yield _a
    while 1:
        _x = _a & -_a
        _y = _a + _x
        _a = (((_a & ~_y) // _x) >> 1) | _y
        if _a >= _ALL: break
        yield _a

n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

MOD=10**9+7
_ALL=1<<n
dp = [0]*(_ALL)
dp[0] = 1

for m in range(1,n+1):
    for a in itercomb(n,m):
        for c,i in enumerate(A[m-1]):
            if (1<<c)&a and i:
                dp[a] += dp[a^(1<<c)]
                if dp[a] > MOD:
                    dp[a] -= MOD


#print(dp)
print(dp[2**n-1])
### BUGGY CODE ###

import decimal
import math

N = int(input())

ans = 0
loop = min(N//2, 10**12)
for i in range(2, loop):
  if N % i == 0:
    ans += 1
    N = (N // i)

print (ans)

### FIXED CODE ###

import decimal
import math

N = int(input())
i = 2
counter = {}
while i * i < N:
  cnt = 0
  while N % i == 0:
    cnt += 1
    N //= i
  counter[i] = cnt
  i += 1

if N != 1:
  counter.setdefault(N, 0)
  counter[N] += 1
#print (counter)

ans = 0

for i, v in counter.items():
  p = 1
  while True:
    if v - p >= 0:
      #print (i**p)
      v -= p
      ans += 1
      p += 1
    else:
      break

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

import numpy as np
n=int(input())
s=[chr(i) for i in range(97, 97+26)]

aa_cij=np.array([[s.index(i)+1  for i in list(input())] for _ in range(n)],dtype='int8')
z=np.zeros((n,n),dtype='int8')
ans=0
for i in range(n):
  aa_cij=np.concatenate( [ aa_cij[1:,:], aa_cij[[0],:] ], axis=0)
  for j in range(n):
    aa_cij=np.concatenate( [ aa_cij[:,1:], aa_cij[:,[0]] ], axis=1)
    if np.allclose(aa_cij - aa_cij.T, z ):
      ans+=1 
print(ans)

### FIXED CODE ###

import numpy as np
n=int(input())
s=[chr(i) for i in range(97, 97+26)]
 
aa_cij=np.array([[s.index(i)+1  for i in list(input())] for _ in range(n)],dtype='int8')
z=np.zeros((n,n),dtype='int8')
ans=0
for i in range(n):
  aa_cij=np.concatenate( [ aa_cij[1:,:], aa_cij[[0],:] ], axis=0)
  if np.allclose(aa_cij - aa_cij.T, z ):
    ans+=1 
print(ans*n)
### BUGGY CODE ###

x = int(input())

if x == 1:
    p = 1
    q = 1
else:
    p = 2
    while True:
        if x % p == 0:
            q = int(x / p)
            break
        else:
            p += 1

ap = p
am = p
bp = 0
bm = 0
while True:
    if ap**4 + ap**3 * bp + ap**2 * bp**2 + ap * bp**3 + bp**4 == q:
        a = ap
        b = bp
        break
    elif am**4 + am**3 * bm + am**2 * bm**2 + am * bm**3 + bm**4 == q:
        a = am
        b = bm
        break
    ap += 1
    bp += 1
    am -= 1
    bm -= 1

print('{} {}'.format(a, b))

### FIXED CODE ###

x = int(input())

if x == 1:
    a = 1
    b = 0
else:
    p = 1
    while True:
        while True:
            if x % p == 0:
                q = int(x / p)
                break
            else:
                p += 1
        ap = p
        am = p
        bp = 0
        bm = 0
        for i in range(200):
            if ap**4 + ap**3 * bp + ap**2 * bp**2 + ap * bp**3 + bp**4 == q:
                a = ap
                b = bp
                break
            elif am**4 + am**3 * bm + am**2 * bm**2 + am * bm**3 + bm**4 == q:
                a = am
                b = bm
                break
            ap += 1
            bp += 1
            am -= 1
            bm -= 1
        else:
            p += 1
            continue
        break

print('{} {}'.format(a, b))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

cnt = 0

for i in range(N // R + 1):
    for j in range(N // G + 1):
        t = N - (i * R + j * G)
        if 0 <= t and t % B == 0:
            cnt += 1
            
print(cnt)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

cnt = 0

for i in range(N // R + 1):
    for j in range(N // G + 1):
        t = N - (i * R + j * G)
        if 0 <= t and t % B == 0:
            cnt += 1
            
print(cnt)
### BUGGY CODE ###

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

pre = ""
suf = "" 
rev = 0
for i in range(Q):
    q = input().split()
    if len(q) == 1:
        rev = (rev + 1) % 2
    else:
        _, f, c = q
        if f == '1':
            if rev == 0:
                pre = c + pre
            else:
                suf = suf + c
        else:
            if rev == 0:
                suf = suf + c
            else:
                pre = c + pre

ans = pre + S + suf
if rev == 0:
    print(ans)
else:
    print(ans[::-1])


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
S = input()
Q = int(input())
#S = "a"*100000
#Q = 200000
pre = ""
suf = ""

rev = 0
for i in range(Q):
    q = input().split()
    '''
    if i % 3 == 0:
        q = ('1')
    if i % 3 == 1:
        q = (2,'1','b')
    if i % 3 == 2:
        q = (2,'2','b')
        '''

    if len(q) == 1:
        rev = (rev + 1) % 2
    else:
        _, f, c = q
        f = f.decode()
        c = c.decode()
        if f == '1':
            if rev == 0:
                pre += c
            else:
                suf += c
        else:
            if rev == 0:
                suf += c
            else:
                pre += c

S = S.decode()[:-1]
ans = pre[::-1] + S + suf
if rev == 0:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

from functools import reduce

n=int(input())
a=list(map(int,input().split()))
ans=reduce(lambda x,y:x*y,a)
if ans <= 10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
limit=10**18
a.sort()
result=a[0]
for k in a[1:]:
    result*=k
    if result > limit:
        print(-1)
        exit()
print(result)
### BUGGY CODE ###

h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=list(input())
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      grid[i][j]="."
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if grid[y][x]=="#":
    continue
  if grid[y][x]==".":
    grid[y][x]="#"
  if y-1>=0:
    que.append([y-1,x,p+1])
  if y+1<h:
    que.append([y+1,x,p+1])
  if x-1>=0:
    que.append([y,x-1,p+1])
  if x+1<w:
    que.append([y,x+1,p+1])
print(max(p-1,0))

### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

# https://atcoder.jp/contests/abc142/tasks/abc142_c

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

ans = str(A_list.index(1) + 1)
for i in range(2, N + 1):
    tmp = str(A_list.index(i) + 1)
    ans = ' '.join([ans, tmp])

print(ans)

### FIXED CODE ###

# https://atcoder.jp/contests/abc142/tasks/abc142_c

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

# ans = str(A_list.index(1) + 1)
# for i in range(2, N + 1):
#     tmp = str(A_list.index(i) + 1)
#     ans = ' '.join([ans, tmp])



ans_list = [0] * N

for i in range(N):
    ans_list[A_list[i] - 1] = i + 1

# リストを空白区切りで出力
print(*ans_list)
### BUGGY CODE ###

#1/A mod p の計算
#フェルマーの小定理より
#1/a=a^(p-2)  (mod p)を用いる。
#つまり、A^(p-2)(mod p)を求める.

def squaremod(A,p,mod):#A^pの計算
    if p==0:
        return 1
    if p%2==1:
        return (A*squaremod(A,p-1,mod))%mod
    if p%2==0:
        return (squaremod(A,p/2,mod) %mod)**2 %mod

    

N,A,B,K=map(int,input().split())
mod=998244353

def factorial(n):
    ANS=1
    for i in range(1,n+1):
        ANS=(ANS*i)%mod

    return ANS
        
    

def Combi(n,r):
    #return factorial(n) // (factorial(n - r) * factorial(r))
    #return factorial(n) * (factorial(n - r) * factorial(r))^(mod -2)
    return factorial(n) *squaremod(factorial(n - r) * factorial(r) %mod ,mod-2,mod)%mod


ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi(N,i)*Combi(N,q)))%mod
        #print(q,r,ANS)

print(ANS)


### FIXED CODE ###

N,A,B,K=map(int,input().split())
mod=998244353

INV=[None]*(N+1)
for i in range(1,N+1):
    INV[i]=pow(i,mod-2,mod)

Combi=[None]*(N+1)
Combi[0]=1
Combi[1]=N
for i in range(2,N//2+2):
    Combi[i]=Combi[i-1]*(N-i+1)*INV[i] %mod
for i in range(N//2+2,N+1):
    Combi[i]=Combi[N-i]


ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi[i]*Combi[q])%mod)%mod

print(ANS)
### BUGGY CODE ###

def main():
    """"ここに今までのコード"""

n = int(input())
A = [int(a) for a in input().split()]
mod=10**9+7

ans=0
for i in range(60):
    l=0
    for j in range(n):
        l+=A[j]%2
        A[j]=A[j]//2
    ans=(ans+l*(n-l)*(2**i))%mod
    

#ans=xor[0]
#for j in range(60-1):
#    ans=((2*ans)+xor[j+1])%mod
print(int(ans)) 

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    """"ここに今までのコード"""
 
n = int(input())
A = [int(a) for a in input().split()]
mod=10**9+7
 
ans=0
for i in range(60):
    l=sum([a%2 for a in A])
    ans=(ans+l*(n-l)*(2**i))%mod
    A=[a//2 for a in A]
    
 
#ans=xor[0]
#for j in range(60-1):
#    ans=((2*ans)+xor[j+1])%mod
print(int(ans)) 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

k = int(input())

cnt = 0
runrun = [1,2,3,4,5,6,7,8,9,10]

i = 1
judge = True
while judge:
    lnum = list(str(i))
    div = True
    for j in range(len(lnum)):
        if len(lnum) == 1:
            break

        str_num = lnum[j:j+2]
        if str_num in runrun:
            next
        else:
            if len(lnum) > 3:
                div = False
                break

        now = lnum[j]
        nxt = (j+1) % len(lnum)
        if nxt == 0:
            break
        nxt = lnum[nxt]

        sum_num = int(now) - int(nxt)
        if abs(sum_num) > 1:
            div = False
            break

    if div:
        cnt += 1
        if cnt == k:
            print(i)
            judge = False
            exit
        runrun.append(str(i))

    i += 1



### FIXED CODE ###

k = int(input())

lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9]


def generate_lunlun(x):
    mod = x % 10

    if mod - 1 >= 0:
        yield x*10 + mod-1

    yield x*10 + mod

    if mod + 1 <= 9:
        yield x*10 + mod + 1


p = 0

while len(lunlun) < k:
    for i in generate_lunlun(lunlun[p]):
        lunlun.append(i)

    p += 1

print(lunlun[k-1])
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
 
q=deque()
 
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
 
dx=[1,0,-1,0]            
dy=[0,1,0,-1]
ans=0
 
while q:
    nq=deque()
    while True:
        y,x=q.popleft()    
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<h and 0<=nx<w and a[ny][nx]!='#':
                a[ny][nx]='#'
                nq.append((ny,nx))

        if not q:
            ans+=1
            q=nq
            break
print(ans-1)

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
field=[[False for i in range(w)] for j in range(h)]
 
q=deque()
 
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            field[i][j]=True
 
dx=[1,0,-1,0]            
dy=[0,1,0,-1]
ans=0
 
while q:
    nq=deque()
    while True:
        y,x=q.popleft()    
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<h and 0<=nx<w and field[ny][nx]==False:
                field[ny][nx]=True
                nq.append((ny,nx))

        if not q:
            ans+=1
            q=nq
            break
print(ans-1)
### BUGGY CODE ###

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

num = 1

for i in range(n):
    num *= a[i]

if num > 10**18:
    print(-1)
else:
    print(num)

### FIXED CODE ###

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

a_sum = 1

if 0 in a:
    print(0)
else:
    for i in range(n):
        a_sum *= a[i]
        if a_sum > 10**18:
            a_sum = -1
            break

    print(a_sum)