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

def popcount(n):
    return bin(n).count('1')

def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)
    pcount_X = popcount(X_int)

    for i,bit in enumerate(X):
        mask = 1 << (N-i-1)
        Xi = X_int ^ mask

        pcount_Xi = pcount_X + (-1)**int(bit)

        n = Xi
        pcount_n = pcount_Xi
        ans = 0
        while n > 0:
            ans += 1
            n %= pcount_n
            pcount_n = popcount(n)
        print(ans)

main()

### FIXED CODE ###

def popcount(n):
    return bin(n).count('1')


def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)

    pcount_X = popcount(X_int)

    pcount_X_pls1 = pcount_X + 1
    pcount_X_mns1 = pcount_X - 1
    
    X_mod_pcount_X_pls1 = X_int % pcount_X_pls1
    if pcount_X_mns1 != 0:
        X_mod_pcount_X_mns1 = X_int % pcount_X_mns1

    for i,bit in enumerate(X):
        bit = int(bit)
        if bit == 0:
            n = (X_mod_pcount_X_pls1 + pow(2, N-i-1, pcount_X_pls1)) % pcount_X_pls1
        else:
            if pcount_X_mns1 == 0:
                print(0)
                continue
            n = (X_mod_pcount_X_mns1 - pow(2, N-i-1, pcount_X_mns1)) % pcount_X_mns1

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()
### BUGGY CODE ###

H,W,M = map(int,input().split())
Hinx = [0 for _ in range(H+1)]
Winx = [0 for _ in range(W+1)]
isExist = []
for i in range(M):
    h,w = map(int,input().split())
    Hinx[h] += 1
    Winx[w] += 1
    isExist.append((h,w))


HMinx = []
WMinx = []
Hmax = max(Hinx)
Wmax = max(Winx)
ans = Hmax + Wmax

isExist = set(isExist)
for i in range(1,H+1):
    if Hinx[i] == Hmax:
        HMinx.append(i)
for i in range(1,W+1):
    if Winx[i] == Wmax:
        WMinx.append(i)

cross = 0
not_cross = 0

for i in HMinx:
    for j in WMinx:
        if (i,j) in isExist:
            cross += 1
        else:
            not_cross += 1

if not_cross > 0:
    print(ans)
else:
    print(ans - 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

class SegmentTree():
    def __init__(self, n, init):
        self.n = 2 ** (n - 1).bit_length()
        self.init = init
        self.data = [init] * (2 * self.n)

    def inc(self, k):
        self.data[k + self.n - 1] += 1

    def build(self):
        for k in reversed(range(self.n - 1)):
            self.data[k] = max(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def update(self, k, a):
        k += self.n - 1
        self.data[k] += a

        while k > 0:
            k = (k - 1) // 2
            self.data[k] = max(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def query(self, l, r):
        L = l + self.n
        R = r + self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = max(ret, self.data[R - 1])
            if L & 1:
                ret = max(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret



if __name__ == "__main__":
    H, W, M = map(int, input().split())

    Seg = SegmentTree(W + 5, 0)

    Yaxis = dict()

    for _ in range(M):
        h, w = map(int, input().split())
        if h in Yaxis: Yaxis[h].append(w)
        else: Yaxis[h] = [w]
        Seg.inc(w)

    Seg.build()


    ans = 0
    for y in Yaxis:
        for x in Yaxis[y]: Seg.update(x, -1)
        ans = max(ans, len(Yaxis[y]) + Seg.query(0, W + 1))
        for x in Yaxis[y]: Seg.update(x, 1)

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

r,g,b,n=map(int,input().split())
nr=n//r
ng=n//g
nb=n//b
ans=0
for i in range(nr+1):
  for j in range(ng+1):
    for k in range(nb+1):
      if i*r+j*g+k*b==n:
        ans+=1
print(ans)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
nr=n//r
ans=0
for i in range(nr+1):
  ng=(n-i*r)//g
  for j in range(ng+1):
    res=n-r*i-g*j
    if res%b==0:
      ans+=1
print(ans)
### BUGGY CODE ###

def get_prime_factorized(N):
    result    = []
    base, exp = 2, 0
    while base ** 2 <= N:
        while N % base == 0:
            N    = N // base
            exp += 1
        if exp > 0:
            result.append([base, exp])
        base, exp = base + 1, 0
    if N > 1:
        result.append([N, 1])
    return result

def re_func_divisior(prime_factorized):
    base, exp = prime_factorized.pop()
    P = re_func_divisior(prime_factorized) if prime_factorized else [[]]
    Q = [[base ** k] for k in range(exp + 1)]
    return [p + q for p in P for q in Q]

def get_list_divisor(N, reverse=True):
    try:
        prime_factorized = get_prime_factorized(N)
        res    = re_func_divisior(prime_factorized)
        result = []
        for k in res:
            for i, x in enumerate(k):
                if i == 0:
                    r = x
                else:
                    r *= x
            result.append(r)
        result = sorted(result, reverse=reverse)
    except:
        result = [N]
    return result


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

X = get_list_divisor(sum(A))

is_break = False

for x in X:
    POS = sorted([a % x for a in A if a % x != 0])
    NEG = [x - pos for pos in POS]
    for sep in range(1, len(POS)):
        if sum(POS[:sep]) == sum(NEG[sep:]) and sum(POS[:sep]) <= K:
            is_break = True
            break
    if is_break:
        break

print(x)


### FIXED CODE ###

import numpy as np


def get_prime_factorized(N):
    result    = []
    base, exp = 2, 0
    while base ** 2 <= N:
        while N % base == 0:
            N    = N // base
            exp += 1
        if exp > 0:
            result.append([base, exp])
        base, exp = base + 1, 0
    if N > 1:
        result.append([N, 1])
    return result

def re_func_divisior(prime_factorized):
    base, exp = prime_factorized.pop()
    P = re_func_divisior(prime_factorized) if prime_factorized else [[]]
    Q = [[base ** k] for k in range(exp + 1)]
    return [p + q for p in P for q in Q]

def get_list_divisor(N, reverse=True):
    try:
        prime_factorized = get_prime_factorized(N)
        res    = re_func_divisior(prime_factorized)
        result = []
        for k in res:
            for i, x in enumerate(k):
                if i == 0:
                    r = x
                else:
                    r *= x
            result.append(r)
        result = sorted(result, reverse=reverse)
    except:
        result = [N]
    return result


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

X = get_list_divisor(sum(A))

is_break = False

for x in X:
    POS = sorted([a % x for a in A if a % x != 0])
    NEG = [x - pos for pos in POS]
    POS_cumsum = np.cumsum(POS)
    NEG_cumsum = np.cumsum(NEG[::-1])[::-1]
    for sep in range(1, len(POS)):
        if POS_cumsum[sep-1] == NEG_cumsum[sep] and POS_cumsum[sep-1] <= K:
            is_break = True
            break
    if is_break:
        break

print(x)
### BUGGY CODE ###

import io
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
2000 3
'''


def MAIN():
  # T_IN()
  A()


def A():
  x = IN_L_I()
  n = x[0]
  k = x[1]

  for i in range(1, k + 1):
    blue = f(k, i)

    red = 0
    red += f(n - k, i - 1)
    red += f(n - k, i)
    red += f(n - k, i)
    red += f(n - k, i + 1)

    res = int((blue * red) % (10 ** 9 + 7))
    print(res)
  return None


def f(x: int, y: int):
  if x < y:
    return 0
  if x == y == 0:
    return 1
  if y < 1:
    return 0
  return f2(x - y, y)


def f2(x: int, y: int):
  return c(x + y - 1, y - 1)


def c(a: int, b: int):
  return pascal(a, b)


@lru_cache(maxsize=None)
def pascal(x, y):
  if x == 0 or y == 0 or x == y:
    return 1
  else:
    return (pascal(x - 1, y - 1) + pascal(x - 1, y)) % (10 ** 9 + 7)


MAIN()


### FIXED CODE ###

import io
import sys

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
2000 3
'''


def MAIN():
  # T_IN()
  cmb_init(MOD)
  A()


def A():
  x = IN_L_I()
  n = x[0]
  k = x[1]

  res = []
  for i in range(1, k + 1):
    blue = f(k, i)

    # red = 0
    # red += f(n - k, i - 1)
    # red += f(n - k, i)
    # red += f(n - k, i)
    # red += f(n - k, i + 1)
    red = f2(n - k - (i - 1), i + 1)

    res.append((blue * red) % MOD)

  [print(i) for i in res]
  return None


def f(x: int, y: int):
  if x < y:
    return 0
  if x == y == 0:
    return 1
  if y < 1:
    return 0
  return f2(x - y, y)


def f2(x: int, y: int):
  return c(x + y - 1, y - 1)


def c(a: int, b: int):
  return cmb(a, b, MOD)


def track(func):
  def tracked(*args, **kwargs):
    result = func(*args, **kwargs)
    name = func.__name__
    arg_str = ",".join(repr(arg) for arg in args)
    print("%s(%s) -> %r" % (name, arg_str, result))
    return result

  return tracked


### CMB ###############################
def cmb(n, r, mod):
  if (r < 0 or r > n):
    return 0
  r = min(r, n - r)
  return g1[n] * g2[r] * g2[n - r] % mod


def cmb_init(mod):
  for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


N = 10 ** 4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

### CMB ###############################


MAIN()
### BUGGY CODE ###

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

already = [0 for i in range(n+1)]
idx = m+1
for sa in range(m)[::-1]:
    sa += 1
    while True:
        if idx-sa < 1:
            idx += 1
            if idx > n: idx = 1
            continue
        if already[idx] == 0 and already[idx-sa] == 0:
            right, left = idx, idx-sa
            already[right], already[left] = 1, 1
            idx += 1
            if idx > n: idx = 1
            break
        else:
            idx += 1
            if idx > n: idx = 1
    print(left, right)

### FIXED CODE ###

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

if m%2 == 0:
    gu_max, ki_max = m, m-1
else:
    gu_max, ki_max = m-1, m
gu_start = 1
ki_start = 1 + gu_max + 1

for sa in range(m)[::-1]:
    sa += 1
    if sa%2 == 0:
        print(gu_start, gu_start+sa)
        gu_start += 1
    else:
        print(ki_start, ki_start+sa)
        ki_start += 1
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
from operator import mul
from functools import reduce
N = I()
A = LI()
ans = reduce(mul, A)
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
A = LI()
ans = A[0]
if 0 in A:
    ans = 0
else:
    for i in range(1, N):
        if ans > 10**18:
            ans = -1
            break
        else:
            ans = ans*A[i]
if ans > 10**18:
    ans = -1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    s = input().strip()
    q = int(input().strip())

    for i in range(q):
        query = input().strip()
        if query[0] == "1":
            s = s[::-1]
        else:
            _, f, c = query.split()
            if f == "1":
                s = c + s
            else:
                s = s + c

    print(s)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    s = input().strip()
    q = int(input().strip())

    rev_count = 0
    s_prev = ""
    s_suffix = ""
    for i in range(q):
        query = input().strip()
        if query[0] == "1":
            rev_count += 1
        else:
            _, f, c = query.split()
            if (f == "1" and rev_count % 2 == 0) or (f == "2" and rev_count % 2 == 1):
                s_prev += c
            else:
                s_suffix += c

    if rev_count % 2 == 0:
        print(s_prev[::-1] + s + s_suffix)
    else:
        print(s_suffix[::-1] + s[::-1] + s_prev)


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

from heapq import heappush, heappop
N=int(input())
road=[[float("inf") for _ in range(N)]for _ in range(N)]
pq=[]
ans=0
for i in range(N):
    road[i][i]=0
    tmp=list(map(int,input().split()))
    for j in range(N):
        heappush(pq,(tmp[j],i,j))

while pq:
    v=heappop(pq)
    d,i,j=v[0],v[1],v[2]
    tmp=road[i][j]
    for k in range(N):
        tmp=min(tmp,road[i][k]+road[k][j])
    if tmp>d:
        road[i][j]=d
        road[j][i]=d
        ans+=d
    elif tmp==d:
        road[i][j]=d
        road[j][i]=d
    else:
        print(-1)
        exit()
print(ans)

### FIXED CODE ###

from heapq import heappush, heappop
def main():
    N=int(input())
    road=[[float("inf") for _ in range(N)]for _ in range(N)]
    pq=[]
    ans=0
    for i in range(N):
        road[i][i]=0
        tmp=list(map(int,input().split()))
        for j in range(i+1,N):
            heappush(pq,(tmp[j],i,j))

    while pq:
        v=heappop(pq)
        d,i,j=v[0],v[1],v[2]
        tmp=road[i][j]
        for k in range(N):
            tmp=min(tmp,road[i][k]+road[k][j])
            if tmp==d:
                break
        if tmp>d:
            road[i][j]=d
            road[j][i]=d
            ans+=d
        elif tmp==d:
            road[i][j]=d
            road[j][i]=d
        else:
            print(-1)
            exit()
    print(ans)
main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
xor = [0] * n
s = [0] * n
xor[0] = a[0]
s[0] = a[0]
for i in range(1, n):
    s[i] = s[i - 1] + a[i]
    xor[i] = xor[i - 1] ^ a[i]

num = 0
for i in range(n):
    for j in range(i, n):
        if i == 0:
            if xor[j] == s[j]:
                num += 1
        elif (xor[j] ^ xor[i - 1]) == (s[j] - s[i - 1]):
            num += 1
        if (xor[j] ^ xor[i - 1]) < (s[j] - s[i - 1]):
            break

print(num)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
s = 0
num = 0
l = 0
for i in range(N):
    while l < N and s + A[l] == s ^ A[l]:
        s += A[l]
        l += 1
    num += l - i
    s -= A[i]

print(num)
### BUGGY CODE ###

N = int(input())
l = sorted(list(map(int, input().split())))

from bisect import bisect_left, bisect_right

cnt = 0
for i in range(N):
    a = l[i]
    for j in range(i, N):
        if i == j:
            continue
        b = l[j]
        l2 = l[j+1:]
        start = bisect_right(l2, b-a)
        end = bisect_left(l2, a+b)
        cnt += len(l2[start:end])
print(cnt)

### FIXED CODE ###

N = int(input())
l = sorted(list(map(int, input().split())))
 
from bisect import bisect_left

cnt = 0
for i in range(N):
    a = l[i]
    for j in range(i+1, N):
        b = l[j]
        cnt += bisect_left(l[j+1:], a+b)
print(cnt)
### BUGGY CODE ###

n = int(input())
nums = []
for i in range(n):
  num = int(input())
  nums.append(num)
count = 0
for j in nums:
  test = nums.count(j)
  if test % 2 == 1:
    count += 1
print(count)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
nums = []
for i in range(n):
  num = int(input())
  nums.append(num)
d = defaultdict(int)
for j in nums:
  d[j] += 1
count = 0
for k in d.values():
  if k % 2 == 1:
    count += 1
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
c=Counter(lis)
dp=[[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0]=0
def dfs(x,y,z):
    if x+y+z>n or (x<0 or y<0 or z<0) or (x>n or y>n or z>n):
        return 0
    elif dp[x][y][z]>=0:
        return dp[x][y][z]
    else:
        dp[x][y][z]=(n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
        return (n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            dfs(i,j,k)
'''print(dp[0])
print(dp[1])
print(dp[2])
print(dp[3])'''
print(dp[c[1]][c[2]][c[3]])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # 0個の皿がx0枚、1個の皿がx1枚、2個の皿がx2枚、3個の皿がx3枚
    # x0=n-x1-x2-x3
    ca={1:a.count(1),2:a.count(2),3:a.count(3)}
    memo=[[[-1]*(n+2) for _ in range(n+2)] for _ in range(n+2)]
    memo[0][0][0]=0
    for x3 in range(ca[3]+1):
        for x2 in range(ca[2]+ca[3]+1-x3):
            for x1 in range(ca[1]+ca[2]+ca[3]+1-x3-x2):
                if (x1,x2,x3)==(0,0,0):continue
                tmp=0
                if x1>0:tmp+=memo[x1-1][x2][x3]*x1
                if x2>0:tmp+=memo[x1+1][x2-1][x3]*x2
                if x3>0:tmp+=memo[x1][x2+1][x3-1]*x3
                tmp+=n
                tmp/=x1+x2+x3
                memo[x1][x2][x3]=tmp
    print(memo[ca[1]][ca[2]][ca[3]])
if __name__=='__main__':
    main()
### BUGGY CODE ###

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

class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

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

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

fr, ba = min(a), max(a)+1

while ba - fr > 1:
	mi = (fr+ba) // 2
	bit = BIT(n+1)
	res = 0
	inv = [0]
	min_tmp = 0
	# あとで全体を-min_tmp+1だけ足さないとバグる
	for j in range(n):
		if a[j] >= mi:
			inv.append(inv[-1]+1)
		else:
			inv.append(inv[-1]-1)
			min_tmp = min(min_tmp, inv[-1])

	for j in range(n+1):
		res += bit.b_sum(inv[j] - min_tmp + 1)
		bit.b_add(inv[j] - min_tmp + 1, 1)

	if res >= (n * (n+1) / 4):
		fr = mi
	else:
		ba = mi

print(fr)

### FIXED CODE ###

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

class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

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

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

fr, ba = min(a), max(a)+1

while ba - fr > 1:
	mi = (fr+ba) // 2
	bit = BIT(n+1)
	res = 0
	inv = [0]
	min_tmp = 0
	# あとで全体を-min_tmp+1だけ足さないとバグる
	for j in range(n):
		if a[j] >= mi:
			inv.append(inv[-1]+1)
		else:
			inv.append(inv[-1]-1)
			min_tmp = min(min_tmp, inv[-1])

	for j in range(n+1):
		res += bit.b_sum(inv[j] - min_tmp + 1)
		bit.b_add(inv[j] - min_tmp + 1, 1)

	if res >= (n * (n+1) / 4):
		fr = mi
	else:
		ba = mi

print(fr)
### BUGGY CODE ###

import numpy as np

n=int(input())
a=np.array(list(map(int,input().split())))
#print(a)

ans=0
for i in range(n):
  b=a[i]%a
  #print(b)
  #print(b==0)
  if np.count_nonzero(b==0)==1:
    ans+=1
print(ans)


### FIXED CODE ###

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

n=int(input())
A=list(map(int,input().split()))
cnt=[0]*(10**6+2)
ans=0
for a in A:
  if cnt[a]!=0:
    cnt[a]=2
    continue
  x=a
  while x<10**6+2:
    cnt[x]+=1
    x+=a
for a in A:
  #print(cnt[a])
  if cnt[a]==1:
    ans+=1
print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
g = [[True]*(w+2)]
for i in range(h):
    g.append([True] + [a == '#' for a in input()] + [True])
g.append([True]*(w+2))

bp = []
for i in range(1, h+1):
    for j in range(1, w+1):
        if g[i][j]:
            bp.append([i, j])

cnt = 0
while bp:
    p = []
    for i, j in bp:
        if not g[i+1][j]:
            g[i+1][j] = True
            p.append([i+1, j])
        if not g[i-1][j]:
            g[i-1][j] = True
            p.append([i-1, j])       
        if not g[i][j+1]:
            g[i][j+1] = True
            p.append([i, j+1])
        if not g[i][j-1]:
            g[i][j-1] = True
            p.append([i, j-1])
    cnt += 1
    bp = p
print(cnt-1)

### FIXED CODE ###

h, w = map(int, input().split())
g = [[True]*(w+2)]
for i in range(h):
    g.append([True] + [a == '#' for a in input()] + [True])
g.append([True]*(w+2))

bp = []
for i in range(1, h+1):
    for j in range(1, w+1):
        if g[i][j]:
            bp.append((i, j))

cnt = 0
while bp:
    p = []
    for i, j in bp:
        if not g[i+1][j]:
            g[i+1][j] = True
            p.append((i+1, j))
        if not g[i-1][j]:
            g[i-1][j] = True
            p.append((i-1, j))       
        if not g[i][j+1]:
            g[i][j+1] = True
            p.append((i, j+1))
        if not g[i][j-1]:
            g[i][j-1] = True
            p.append((i, j-1))
    cnt += 1
    bp = p
print(cnt-1)
### BUGGY CODE ###

#
import sys
import math
import itertools

n = int(input())

# 素因数分解
def factorialization(n):
    a = []
    t = n
    for i in range(2,int(n**0.5)+1):
        if t%i == 0:
            e = 0
            while t%i ==0:
                e += 1
                t = t // i
            a.append([i,e])
    if t > 1:
        a.append([t,1])
    return a

answer=0

for c in range(1,n):
    ff=1
#    print(factorialization(c))
    for p in factorialization(c):
        ff *= (p[1]+1)
    answer += ff

print(answer)


### FIXED CODE ###

#
import sys
import math
import itertools

n = int(input())

answer =0

for a in range(1,n):
    answer += ((n-1)//a)

print(answer)
### BUGGY CODE ###

n=int(input())
MOD=10**9+7
a=list(map(int,input().split()))
x=[0 for i in range(60)]
for i in range(n):
    s=(bin(a[i])[2:])[::-1]
    for j in range(len(s)):
        if s[j]=='1': x[j]+=1

ans=0
q=1
for i in range(60):
    ans+=((((n-x[i] )*x[i])%MOD)*q)%MOD
    ans=ans%MOD
    q=(q*2)%MOD
print(ans)

### FIXED CODE ###

def main():
    MOD=10**9+7
    n=int(input())
    x=[0 for i in range(60)]
    a=list(map(int,input().split()))

    for i in range(n):
        k=0
        while a[i]>0:
            if a[i]&1:
                x[k]+=1
            a[i]>>=1
            k+=1
    ans=0
    b=1
    for i in range(60):
        ans+=x[i]*(n-x[i])*b
        ans%=MOD
        b=(b*2)%MOD
    print(ans)


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

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 7+1000000000

amari = 0

for i in range(n):
    aa = 0
    for e in range(n-i-1):
        j = i+e+1
        if i != j:
            aa = aa + a[j]
    number = number + (a[i] * aa)
    number = number % mod
amari = number % mod
print(amari)


### FIXED CODE ###

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 1000000007

amari = 0

all_a = 0

for i in range(n):
    all_a = all_a + a[i]

for i in range(n):
    all_a = all_a - a[i]
    number = number + (a[i] * all_a)
    number = number % mod
amari = number % mod
print(amari)