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

from collections import deque


def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, input().split())
    total_cells = H * W
    existing_black_cells = 0

    grid = [['' for _ in range(W)] for _ in range(H)]
    for i in range(H):
        line = input()
        for j in range(W):
            grid[i][j] = line[j]
            if line[j] == '#':
                existing_black_cells += 1

    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    movement = 0

    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)): # Process same level
            coodinate = queue.popleft()
            visited.add(coodinate)
            y = coodinate[0]
            x = coodinate[1]

            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return

            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x+dx
                Y = y+dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and adjacent not in visited and grid[Y][X] == '.':
                    queue.append(adjacent)
    print(-1)
    return
main()

### FIXED CODE ###

import sys
from collections import deque
    
def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, sys.stdin.readline().split())
    total_cells = H * W
    existing_black_cells = 0
 
    grid = []
    for i in range(H):
        line = sys.stdin.readline()
        existing_black_cells += line.count('#')
        grid.append(line)
 
    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    visited.add((0, 0))
    movement = 0
 
    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            y = coodinate[0]
            x = coodinate[1]
 
            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return
 
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
                    visited.add(adjacent)
    print(-1)
    return
main()
### BUGGY CODE ###

def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    N = I()
    S = SI()
    Q = I()
    K = LI()
    ans = []
    for k in K:
        D = 0; M = 0; C = 0
        now = 0
        for i, s in enumerate(S):
            if s == "D":
                D += 1
            elif s == "M":
                M += 1
                now += D
            elif s == "C":
                C += now
            if i>=k-1:
                if S[i-k+1] == "D":
                    D -= 1
                    now -= M
                elif S[i-k+1] == "M":
                    M -= 1
#        print(D, M, C)
#        ans.append(C)
        print(C)
#    for v in ans:
#        print(v)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

### FIXED CODE ###

def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    N = I()
    S = SI()
    Q = I()
    K = LI()
    ans = []
    for k in K:
        D = 0; M = 0; C = 0
        now = 0
        for i in range(N):
            s = S[i]
            if s == "D":
                D += 1
            elif s == "M":
                M += 1
                now += D
            elif s == "C":
                C += now
            if i>=k-1:
                if S[i-k+1] == "D":
                    D -= 1
                    now -= M
                elif S[i-k+1] == "M":
                    M -= 1
#        print(D, M, C)
#        ans.append(C)
        print(C)
#    for v in ans:
#        print(v)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""
### BUGGY CODE ###

import sys
n,k=map(int,input().split())
hlist=list(map(int,input().split()))
 
mins=[0,abs(hlist[1]-hlist[0])]

if n == 2:
	print(abs(hlist[1]-hlist[0]))
	sys.exit()

for i in range(2,n):
	smallest=10**12
	tmp=hlist[i]
	for j in range(min(k,i)):
		smallest=min(smallest,mins[i-j-1]+abs(tmp-hlist[i-j-1]))
	mins.append(smallest)
	

print(mins[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
hlist=list(map(int,input().split()))
 
mins=[0]
 
for i in range(1,n):
	if i == 1:
		mins.append(abs(hlist[1]-hlist[0]))
		continue
	
	tmplist=[]
	tmp=hlist[i]
	for j in range(min(k,i)):
		tmplist.append(mins[i-j-1]+abs(tmp-hlist[i-j-1]))
	mins.append(min(tmplist))
 
print(mins[n-1])
### BUGGY CODE ###

X, K, D = map(int, input().split())

for k in range(K):
    if min(abs(X+D), abs(X-D)) < abs(X):
        X = min(abs(X+D), abs(X-D))
        K -= 1
    else:
        if K%2 == 0:
            print(X)
            break
        else:
            X = min(abs(X+D), abs(X-D))
            print(X)
            break

if K == 0:
    print(X)


### FIXED CODE ###

X, K, D = map(int, input().split())
S = abs(X)//D

if abs(X)/D >= K:
    X = abs(X)-D*K
    print(X)
else:
    X = min(abs(X-D*S), abs(X+D*S))
    K = K - S
    for k in range(K):
        if min(abs(X+D), abs(X-D)) < abs(X):
            X = min(abs(X+D), abs(X-D))
            K -= 1
        else:
            if K%2 == 0:
                print(X)
                break
            else:
                X = min(abs(X+D), abs(X-D))
                print(X)
                break

    if K == 0:
        print(X)
### BUGGY CODE ###

import bisect
n=int(input())
lists=list(map(int,input().split()))
listss=sorted(lists)
count=0
for i in range(n):
    for j in range(n):
        if i!=j:
            index1= bisect.bisect_left(listss, abs(listss[j]-listss[i])+1)
            index2=bisect.bisect_right(listss,listss[i]+listss[j]-1)
            count+=(index2-index1)
            x=abs(listss[j]-listss[i])
            if  x+1<=listss[i]:
                count-=1
            if x+1<=listss[j]:
                count-=1
print(count//6)
            
    
        

### FIXED CODE ###

import bisect
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists)

cnt=0
import math
for i in range(n):
    for j in range(i+1,n):
        #i<j 
        x=lists[i]
        y=lists[j]
        left=i 
        right=j 
        index=bisect.bisect_right(lists,y-x)
        cnt+=min(j-i-1,j-index)

print(cnt)
### BUGGY CODE ###

while True:
    z=input()
    if z==0:break
    z3=pow(z,3)
    maxInt=0
    for x in range(1,z):
        x3=pow(x,3)
        for y in range(1,z):
            y3=pow(y,3)
            if x3+y3<=z3:
                maxInt=max(maxInt,x3+y3)
    print z3-maxInt

### FIXED CODE ###

from bisect import bisect
L=[0]*1112
y=[pow(i,3) for i in range(1,1111)]
for z in range(1,1112):
    z3=pow(z,3)
    maxInt=0
    for x in range(1,z):
        x3=pow(x,3)
        diff=z3-x3
        y3=y[bisect(y,diff)-1]
        maxInt=max(maxInt,x3+y3)
    L[z]=z3-maxInt
while True:
    z=input()
    if z==0:break
    print L[z]
### BUGGY CODE ###

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

area = []
for i in range(K):
    L, R = map(int, input().split())
    area.append((L, R))

d = [0] * N


def func(pos):
    for a in area:
        for i in range(a[0], a[1]+1):
            if pos - i > -1:
                d[pos-i] += d[pos] % 998244353
            else:
                break


d[N-1] = 1
for i in range(N-1, -1, -1):
    if d[i] > 0:
        func(i)

print(d[0] % 998244353)


### FIXED CODE ###

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

area = []
for i in range(K):
    L, R = map(int, input().split())
    area.append((L, R))

area.sort()
d = [0] * N
a = [0] * N


def func(pos):
    for l, r in area:
        if pos + l - 1 < N:
            a[pos + l-1] += d[pos]
        if pos + r < N:
            a[pos + r] -= d[pos]
    d[pos+1] = (d[pos] + a[pos]) % 998244353


d[0] = 1
a[0] = -1
for i in range(0, N-1):
    func(i)

print(d[N-1] % 998244353)
### BUGGY CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def modInverse(a, p):
    return pow(a, p - 2, p)


@lru_cache(maxsize=None)
def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % p

    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % p

    return (numerator * modInverse(denominator, p)) % p


def main():
    N, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    a = min(N - 1, K)

    ans = 1
    for i in range(1, a + 1):
        ans += modBinomial(N, i, MOD) * modBinomial(N - 1,  N - i - 1, MOD)

    print(ans % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

def cmb(n, r, p):
    global fact, factinv
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


def main():
    N, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    a = min(N - 1, K)

    global fact, factinv, inv
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

    ans = 1
    for i in range(1, a + 1):
        ans += cmb(N, i, MOD) * cmb(N - 1, N - i - 1, MOD) % MOD

    print(ans % MOD)


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

n,k=map(int,input().split())
h=[0]*n
h=list(map(int,input().split()))


ans=[0]*n

ans[0]=0
ans[1]=abs(h[1]-h[0])

for i in range(2,n):
  if (k==1):
    ans[i]=ans[i-1]+abs(h[i]-h[i-1])
  else:
    j=1
    check=max(h)
    while j<=k and i-j>=0:
      check=min(check,ans[i-j]+abs(h[i]-h[i-j]))
      j+=1
    ans[i]=check

print(ans[n-1])

### FIXED CODE ###

import sys
import numpy as np

input=sys.stdin.readline

n,k=map(int,input().split())
h=[0]*n
h=list(map(int,input().split()))

dp=np.zeros(n,dtype=int)
h=np.array(h)

for i in range(1,n):
  start=max(0,i-k)
  dp[i]=min(dp[start:i] + np.abs(h[i]-h[start:i]))

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

n = int(input())
a = list(map(int, input().split()))
INF = 1000000000000000000
ans = 1
flag = 0

for cnt in range(n):
    ans *= a[cnt]

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

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
INF = 1000000000000000000
ans = 1
flag = 0

for cnt in range(n):
    if a[cnt] == 0:
        print(0)
        flag = 1
        break

if flag == 0:
    for cnt in range(n):
        ans *= a[cnt]
        if ans > INF:
            print(-1)
            flag = 1
            break

if flag == 0:
    print(ans)
### BUGGY CODE ###

n = int(input())
a_list = [int(num) for num in input().split(" ")]
a_set = set(a_list)
total_comb = 0
for i in a_set:
    i_count = a_list.count(i)
    total_comb += i_count*(i_count-1)
total_comb = int(total_comb/2)
for k in range(n):
    except_num = a_list[k]
    print(total_comb - (a_list.count(except_num)-1))


### FIXED CODE ###

import collections

n = int(input())
a_list = [int(num) for num in input().split(" ")]
c_dict = collections.Counter(a_list)

total_comb = 0
for i in c_dict:
    i_count = c_dict[i]
    total_comb += int(i_count*(i_count-1)/2)
for k in range(n):
    except_num = a_list[k]
    print(total_comb - (c_dict[except_num]-1))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
from collections import Counter
ctr = Counter(A)

def is_ok(k):
    ctr[k] -= 1
    d = 1
    while d*d <= k:
        if k%d==0:
            if ctr[d] > 0:
                ctr[k] += 1
                return False
            if ctr[k//d] > 0:
                ctr[k] += 1
                return False
        d += 1
    ctr[k] += 1
    return True

ans = 0
for k,v in ctr.items():
    if v > 1: continue
    if is_ok(k):
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
from collections import Counter
ctr = Counter(A)
B = [k for k,v in ctr.items() if v == 1]
B.sort()
D = {b:i for i,b in enumerate(B)}

ok = [1] * len(B)
MX = 10**6+1
for k in ctr.keys():
    for n in range(2*k,MX,k):
        if n in D:
            ok[D[n]] = 0
print(sum(ok))
### BUGGY CODE ###

h, w = list(map(int, input().split()))
si, sj = list(map(lambda x: int(x)-1, input().split()))
ti, tj = list(map(lambda x: int(x)-1, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 探索時に移動する方向
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

# 距離情報を一番遠い値で初期化
import numpy as np
INF = int(1e9)
dist = np.full((h, w), INF)
#dist = [[INF for j in range(w)] for i in range(h)]

from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    (i, j) = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(di)):
        ni, nj = i+di[v], j+dj[v]
        if (ni<0 or ni>=h or nj<0 or nj>=w):
            continue # マップの境界
        if (s[ni][nj] == '#'):
            continue # 壁
        if (dist[ni][nj]<=d):
            continue # 探索済みコスト以上
        dist[ni][nj] = d
        q.appendleft((ni, nj))
    # 移動Bによるコスト
    for ei in range(-2, 3):
        for ej in range(-2, 3):
            ni, nj = i+ei, j+ej
            if (ni<0 or ni>=h or nj<0 or nj>=w):
                continue # マップの境界
            if (s[ni][nj] == '#'):
                continue # 壁
            if (dist[ni][nj]<=d):
                continue # 探索済みコスト以上
            dist[ni][nj] = d+1
            q.append((ni, nj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)


### FIXED CODE ###

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+2, w+2), INF)
dist = [[INF for j in range(w+2)] for i in range(h+2)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i][0] = 0
    dist[i][-1] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[-1][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)
### BUGGY CODE ###

#
N=int(input())
S=[]
for i in range(N):
    S.append(input())
ans=[]

"""""#
while len(S):
    if len(S)==1:
        x = [S.pop(-1), 1]
        ans.append(x)
        break
    x = [S.pop(-1), 1]
    for i in S[:]:
        if x[0] == i:
            S.remove(i)
            x[1]+=1
    ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])

"""

import queue

q=queue.Queue()
for i in S:
    q.put(i)

while not q.empty():
    x = [q.get(), 1]
    if len(ans)==0:
        ans.append(x)
        continue
    t=0
    for i in range(len(ans)):
        if x[0] == ans[i][0]:
            ans[i][1]+=1
            t+=1
            break
    if t==0:
        ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])










### FIXED CODE ###

#
N=int(input())
S={}
for i in range(N):
    x=input()
    if x in S:
        S[x]+=1
    else:
        S[x]=1
t=max(S.values())
ans=[k for (k,v) in S.items() if v==t]
ans.sort()

for i in ans:
    print(i)
""""
#
while len(S):
    if len(S)==1:
        x = [S.pop(), 1]
        ans.append(x)
        break
    x = [S.pop(), 1]
    for i in S[:]:
        if x[0] == i:
            S.remove(i)
            x[1]+=1
    ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])



import queue

q=queue.Queue()
for i in S:
    q.put(i)

while not q.empty():
    x = [q.get(), 1]
    if len(ans)==0:
        ans.append(x)
        continue
    t=0
    for i in range(len(ans)):
        if x[0] == ans[i][0]:
            ans[i][1]+=1
            t+=1
            break
    if t==0:
        ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])

"""
### BUGGY CODE ###

import numpy as np

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

def mal():
  val=1
  x=0
  while True:
    val*=a[x]
    x+=1
    if x==n:
      if val>10**18:
        print(-1)
      else:
        print(val)
    yield x

mal()
for i in mal():
  if i==n:
    break

### FIXED CODE ###

_=input()
val=1
t=10**18

for i in map(int,input().split()):
  if i==0:
    val*=i
    break
  if val>=t: continue
  val*=i

if val>t:
  print(-1)
  exit()

print(val)
### BUGGY CODE ###

SIZE=2*10**6; MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    fac[i] = fac[i-1]*i%MOD
finv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(SIZE-1,0,-1):
    finv[i-1] = finv[i]*i%MOD
    inv[i] = finv[i]*fac[i-1]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0



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

k, = map(int,readline().split())
s = input()

MOD = 10**9+7

l = len(s)
ans = pow(26,l+k,MOD)
for p in range(l):
    ans -= pow(25,k+l-p)*choose(l+k,p)

print(ans%MOD)






### FIXED CODE ###

SIZE=2*10**6; MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    fac[i] = fac[i-1]*i%MOD
finv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(SIZE-1,0,-1):
    finv[i-1] = finv[i]*i%MOD
    inv[i] = finv[i]*fac[i-1]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0



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

k, = map(int,readline().split())
s = input()

MOD = 10**9+7

l = len(s)
ans = pow(26,l+k,MOD)

p25 = [1]
for _ in range(SIZE):
    p25.append(p25[-1]*25%MOD)

for p in range(l):
    ans -= p25[k+l-p]*choose(l+k,p)%MOD

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    l1 = [0]*61
    for i in a:
        cnt = 0
        k = 1
        while k <= i:
            if i & k == k:
                l1[cnt] += 1
            cnt += 1
            k *= 2
    l0 = [n-i for i in l1]
    ans = 0
    mod = 10**9+7
    for i in range(len(l1)):
        ans = (ans+l0[i]*l1[i]*pow(2, i, mod)) % mod
    print(ans)
main()

### FIXED CODE ###

def main():
    n=int(input())
    a=list(map(int,input().split()))
    l1=[0]*61
    for i in a:
        j=list(reversed(bin(i)[2:]))
        for k in range(len(j)):
            if j[k]=="1":
                l1[k]+=1
    l0=[n-i for i in l1]
    ans=0
    mod=10**9+7
    for i in range(len(l1)):
        ans=(ans+l0[i]*l1[i]*pow(2,i,mod))%mod
    print(ans)
main()
### BUGGY CODE ###

n=int(input())
s=input()
r_list=[]
g_list=[]
b_list=[]
for i in range(len(s)):
    if s[i]=="R":
        r_list.append(i)
    elif s[i]=="G":
        g_list.append(i)
    elif s[i]=="B":
        b_list.append(i)

count=0
for i in range(len(r_list)):
    for j in range(len(g_list)):
        for k in range(len(b_list)):
            mx=max(r_list[i],g_list[j],b_list[k])
            mn=min([r_list[i],g_list[j],b_list[k]])
            middle=r_list[i]+g_list[j]+b_list[k]-mx-mn
            if middle-mn != mx-middle:
                count+=1

print(count)

### FIXED CODE ###

n=int(input())
s=input()
count=0
r_list=[]
g_list=[]
b_list=[]
for i in range(len(s)):
    if s[i]=="R":
        r_list.append(i)
    elif s[i]=="G":
        g_list.append(i)
    elif s[i]=="B":
        b_list.append(i)

for i in range(1,len(s)-1):
    if n%2==0:
        if i<n//2:
            for j in range(1,i+1):
                if s[i]!=s[i-j] and s[i]!=s[i+j] and s[i+j]!=s[i-j]:
                    count+=1
        else:
            for j in range(1,n-i):
                if s[i]!=s[i-j] and s[i]!=s[i+j] and s[i+j]!=s[i-j]:
                    count+=1
    else:
            if i<(n-1)//2:
                for j in range(1,i+1):
                    if s[i]!=s[i-j] and s[i]!=s[i+j] and s[i+j]!=s[i-j]:
                        count+=1
            elif i==(n-1)//2:
                for j in range(1,n-i):
                    if s[i]!=s[i-j] and s[i]!=s[i+j] and s[i+j]!=s[i-j]:
                        count+=1
            elif i>(n-1)//2:
                for j in range(1,n-i):
                    if s[i]!=s[i-j] and s[i]!=s[i+j] and s[i+j]!=s[i-j]:
                        count+=1

print(len(r_list)*len(g_list)*len(b_list)-count)
### BUGGY CODE ###

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

li = []
li_2 = []
li_3 = []
count = 0
for i in A:
    li.append(i)
    li_2.append(i)
    li_3.append(i)
    li_2.sort()
    li_3.sort(reverse=True)
    if li != li_2 and li != li_3:
        count += 1
        li = [i]
        li_2 = [i]
        li_3 = [i]

print(count+1)


### FIXED CODE ###

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

p = A[0]
count = 0
b = 0
c = 0
for i in range(1,N):
    a = A[i]
    b += a-p
    c += abs(a-p)
    if abs(b) != c:
        count += 1
        b = 0
        c = 0
    p = a
print(count+1)