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

N = int(input())
x = list(map(int, input().split()))
cnt = 0
mn_lst = []
for i in x:
    cnt = 0
    while i % 2 == 0:
        cnt += 1
        i <<= 1
    mn_lst.append(cnt)
print(min(mn_lst))

### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
mn_lst = []
for i in x:
    cnt = 0
    while i % 2 == 0:
        cnt += 1
        i >>= 1
    mn_lst.append(cnt)
    
print(min(mn_lst))
### BUGGY CODE ###

f=lambda:map(int,input().split())
x,y,a,b,c=f()
p=sorted(f())[::-1]
q=sorted(f())[::-1]
r=sorted(f())[::-1]
lp,lq,lr=[0]*(a+1),[0]*(b+1),[0]*(c+1)
s=t=u=m=0
for i in range(a): s+=p[i]; lp[i+1]+=s
for i in range(b): t+=q[i]; lq[i+1]+=t
for i in range(c): u+=r[i]; lr[i+1]+=u
for i in range(min(x,c)+1):
  for j in range(min(y,c-i)+1):
    m=max(m,lp[x-i]+lq[y-j]+lr[i+j])
print(m)

### FIXED CODE ###

f=lambda:map(int,input().split())
x,y,a,b,c=f()
l=sorted(sorted(f())[-x:]+sorted(f())[-y:]+list(f()))
print(sum(l[-x-y:]))
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()

# print(A,B,C)


sum = 0
for b in B:
    sum += len(
        [x for x in A if x < b]
    ) * len (
        [x for x in C if x > b]
    )

# for c in C:
#     for b in [x for x in B if x < c]:
#         for a in [x for x in A if x < b]:

print(sum)

### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()

import bisect
A2 = []
B2 = []
C2 = []
# for a,b,c in zip(A,B,C):
#     bisect.insort_left(A2, a)
#     # bisect.insort_left(B2, b)
#     bisect.insort_left(C2, c)
# print(A,B,C)
# import numpy as np

sum = 0
for b in B:
    sum += bisect.bisect_left(A, b) * (N - bisect.bisect_right(C, b))

# for c in C:
#     for b in [x for x in B if x < c]:
#         for a in [x for x in A if x < b]:

print(sum)
### BUGGY CODE ###

import fractions
import math
import itertools
from functools import reduce

k = int(input())

seq = []
ran = range(1, k + 1)
for i in ran:
    for j in ran:
        for k in ran:
            n = reduce(lambda x, y: math.gcd(x, y), (i, j, k))
            seq.append(n)

print(sum(seq))

### FIXED CODE ###

from math import gcd
from collections import defaultdict

k = int(input())

memo = defaultdict(defaultdict)

rg = range(1, k + 1)
for i in rg:
    for j in rg:
        memo[i][j] = memo[j][i] = gcd(i, j)

ret = 0
for i in rg:
    for j in rg:
        tmp = memo[i][j]
        for k in rg:
            res = memo[k][tmp]
            ret += res

print(ret)
### BUGGY CODE ###

x,y,a,b,c = map(int,input().split())
p = input().split()
p = [int(s) for s in p]
q = input().split()
q = [int(s) for s in q]
r = input().split()
r = [int(s) for s in r]
reds = sorted(p,reverse=True)
reds = reds[:x]
greens = sorted(q,reverse=True)
greens = greens[:y]
r = sorted(r,reverse=True)
while len(r) > 0 and (r[0] > reds[x-1] or r[0] > greens[y-1]):
    if(reds[x-1] > greens[y-1]):
        del greens[y-1]
        greens.insert(0,r.pop(0))
    else:
        del reds[x-1]
        reds.insert(0,r.pop(0))

print(sum(reds)+sum(greens))

### FIXED CODE ###

x,y,a,b,c = map(int,input().split())
p = input().split()
p = [int(s) for s in p]
q = input().split()
q = [int(s) for s in q]
r = input().split()
r = [int(s) for s in r]
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
s = p[:x] + q[:y] + r
s.sort(reverse=True)
print(sum(s[:x+y]))
### BUGGY CODE ###

n=int(input())
import fractions 
from functools import reduce
arr = list(map(int,input().split()))


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

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
    
a = lcm(arr)
ans = []
for i in arr:
    ans.append((a//i)%1000000007)

print(sum(ans)%1000000007)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
 
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
 
a = 1
for i in range(N):
    a = lcm(a, A[i])
 
ans = 0
for i in range(N):
    ans += a * pow(A[i], mod-2, mod)
 
print(ans % mod)
### BUGGY CODE ###


ss = input()
l = [0 for i in range(len(ss))]

for i, s in enumerate(ss):
  p = i
  while ss[p] == ss[i]:
    p = p + (1 if ss[p] == "R" else -1)

  if (p-i)%2 == 0:
    l[p] = l[p] +1
  elif ss[p] == "L":
    l[p-1] = l[p-1] +1
  else:
    l[p+1] = l[p+1] +1

print(" ".join([str(c) for c in l]))

### FIXED CODE ###


ss = input()
lr = [1]
ans = [0] * len(ss)

for s in ss[1:]:
  if lr[-1] > 0:
    if s == "R":
      lr[-1] += 1
    else:
      lr.append(-1)
  else:
    if s == "L":
      lr[-1] -= 1
    else:
      lr.append(1)

i = 0
for num in lr:
  is_r = (num > 0)
  num = abs(num)
  half = num // 2
  if is_r:
    i += num
    ans[i-1] += num - half
    ans[i] += half
  else:
    ans[i-1] += half
    ans[i] += num - half
    i += num

print(" ".join([str(c) for c in ans]))
### BUGGY CODE ###

n,m=[int(x) for x in input().rstrip().split()]
l=[[]*n for x in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)

done=[False for i in range(n)]
dist=[0 for i in range(n)]
ans=[0 for i in range(n)]
def bfs():
  stack=[0]
  dist[0]=0
  done[0]=True
  while(stack):
    now=stack.pop(0)
    done[now]=True
  
    for i in l[now]:
      if done[i]==True or i in stack:
        continue
      dist[i]=dist[now]+1
      ans[i]=now+1
      stack.append(i)

bfs()
print("Yes")
for i in range(1,n):
  print(ans[i])




### FIXED CODE ###

n,m=[int(x) for x in input().rstrip().split()]
l=[[] for x in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)

done=[False for i in range(n)]
ans=[0 for i in range(n)]
def bfs():
  stack=[0]
  done[0]=True
  while(stack):
    now=stack.pop(0)
    done[now]=True
  
    for i in l[now]:
      if done[i]==True:
        continue
      ans[i]=now+1
      done[i]=True
      stack.append(i)

bfs()
print("Yes")
print(*ans[1:])
### BUGGY CODE ###

n = int(input())
l = [0]+list(map(int,input().split()))+[0]
s = 0
while len(set(l))!=1:
  for i in range(n+1):
    if l[i]==0:
      if l[i+1]==0:
          break
      for j in range(i+1,n+2):
        if l[j]!=0:
          l[j] -=1
          continue
        else:
          s += 1
          break
print(s)


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
c = 0
if n==1:
  print(*l)
  exit()
while l.count(0)!=n:
  for i in range(n-1):
    if l[i]==0 and i!=n-2:
      continue
    elif l[i]==0 and i==n-2:
      c += 1
      l[n-1] -=1
    elif l[i]<=l[i+1] and i!=n-2:
      l[i] -= 1
    elif l[i]<=l[i+1] and i==n-2:
      l[i] -= 1
      l[i+1] -=1
      c += 1
    else:
      c += 1
      l[i] -= 1
      break
print(c)
### BUGGY CODE ###

import itertools
S=input()
T=input()

Slist=list(itertools.permutations(list(S),len(S)))
Tlist=list(itertools.permutations(list(T),len(T)))

if "".join(sorted(Slist)[0])<"".join(sorted(Tlist)[-1]):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import itertools
s=input()
t=input()
S="".join(sorted(list(s)))
T="".join(sorted(list(t)))[::-1]
if S<T:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
dp = [[{} for _ in range(W)] for _ in range(H)]
dp[0][0][abs(A[0][0]-B[0][0])] = 0
for h in range(H):
    for w in range(W):
        for v in dp[h][w]:
            if w != W-1:
                v1 = v+A[h][w+1]-B[h][w+1]
                v2 = v-A[h][w+1]+B[h][w+1]
                if v1<0:
                    v1 *= -1
                if v2<0:
                    v2 *= -1
                dp[h][w+1][v1] = 0
                dp[h][w+1][v2] = 0
            if h != H-1:
                v1 = v+A[h+1][w]-B[h+1][w]
                v2 = v-A[h+1][w]+B[h+1][w]
                if v1<0:
                    v1 *= -1
                if v2<0:
                    v2 *= -1
                dp[h+1][w][v1] = 0
                dp[h+1][w][v2] = 0
ans = min(dp[H-1][W-1])
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
def cal():
    dp1 = [set() for _ in range(W)]
    dp2 = [set() for _ in range(W)]
    for h in range(H):
        for w in range(W):
            d = D[h][w]
            if h==0 and w==0:
                dp2[0].add(d)
            for v in dp1[w]:
                v1 = v+d
                v2 = v-d if v>=d else -v+d
                dp2[w].add(v1)
                dp2[w].add(v2)
            if 0 < w:
                for v in dp2[w-1]:
                    v1 = v+d
                    v2 = v-d if v>=d else -v+d
                    dp2[w].add(v1)
                    dp2[w].add(v2)
        dp1 = dp2
        dp2 = [set() for _ in range(W)]
    return min(dp1[W-1])
ans = cal()
print(ans)
### BUGGY CODE ###

N, M  = map(int, input().split())
a  = []
for _ in range(M):
  a.append(int(input()))
sdic  = {}
ans = 0
sdic[N] = 1
sdic[N+1] = 0
for n in reversed(range(N)):
  if n in a:
    sdic[n] = 0
    continue
  t = sdic[n+1] + sdic[n+2]
  if t == 0:
    print(0)
    quit()
  sdic[n] = t
  
print(sdic[0]%1000000007)

### FIXED CODE ###

N, M  = map(int, input().split())
a  = {}
for _ in range(M):
  a[int(input())] = 1
sdic  = {}
nn1 = 1
nn2 = 0
for n in reversed(range(N)):
  if n in a:
    nn2 = nn1
    nn1 = 0
    continue
  t = nn1 + nn2
  if t == 0:
    print(0)
    quit()
  nn2 = nn1
  nn1 = t
  
print(nn1%1000000007)
### BUGGY CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,l[i][0]-1,-1):
        dp[j]=max(dp[j],dp[j-l[i][0]]+l[i][1])
print(dp[-1])

### FIXED CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
l1,l2,l3,l4=[],[],[],[]
a=l[0][0]
for i in range(n):
    if l[i][0]==a:
        l1.append(l[i][1])
    elif l[i][0]==a+1:
        l2.append(l[i][1])
    elif l[i][0]==a+2:
        l3.append(l[i][1])
    else:
        l4.append(l[i][1])
l1.sort(reverse=True)
l2.sort(reverse=True)
l3.sort(reverse=True)
l4.sort(reverse=True)
ans=0
for h in range(len(l1)+1):
    for i in range(len(l2)+1):
        for j in range(len(l3)+1):
            for k in range(len(l4)+1):
                if a*h+(a+1)*i+(a+2)*j+(a+3)*k<=w:
                    ans=max(ans,sum(l1[:h])+sum(l2[:i])+sum(l3[:j])+sum(l4[:k]))
print(ans)
### BUGGY CODE ###

def gcd(a,b):
    if b == 0:
        return abs(a)
    else:
        return gcd(b, a%b)

N,M = map(int, input().split())
S = input()
T = input()


if S[0] != T[0]:
    print(-1)
    exit()

if len(S) == len(T):
    if S == T:
        print(len(S))
    else:
        print(-1)
    exit()

gcd1 = gcd(len(S), len(T))
lcm = len(S)*len(T) // gcd1

SS = []
TT = []
i = 0
j = 0
while i < N:
    SS.append(i*lcm//N + 1)
    i += 1
while j < M:
    TT.append(j*lcm//M + 1)
    j += 1


for i,v in enumerate(SS):
    if v in TT:
        if S[i] == T[TT.index(v)]:
            continue
        else:
            print(-1)
            exit()
print(lcm)


### FIXED CODE ###

import bisect

def gcd(a,b):
    if b == 0:
        return abs(a)
    else:
        return gcd(b, a%b)

N,M = map(int, input().split())
S = input()
T = input()


if S[0] != T[0]:
    print(-1)
    exit()

if len(S) == len(T):
    if S == T:
        print(len(S))
    else:
        print(-1)
    exit()

gcd1 = gcd(len(S), len(T))
lcm = len(S)*len(T) // gcd1

SS = []
TT = []
i = 0
j = 0
while i < N:
    SS.append(i*lcm//N + 1)
    i += 1
while j < M:
    TT.append(j*lcm//M + 1)
    j += 1

ind = 0
ind_max = j-1

for i,v in enumerate(SS):
    ind = bisect.bisect_left(TT, v,ind, j)
    if ind == j:
        break
#    print(ind)
    if TT[ind] == v:
        if S[i] == T[ind]:
            continue
        else:
            print(-1)
            exit()
print(lcm)
### BUGGY CODE ###

#!python
# -*- coding: utf-8 -*-

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

a = 0
I = []
for b in A + [0]:
    I.append(b - a)
    a = b
S = sum(map(abs, I))

for i in range(N):
    j = i + 1
    A_ = [0] + A + [0]
    if A_[j - 1] <= A_[j] <= A_[j + 1]:
        print(S)
    else:
        I_ = I[:]
        I_[i] = I_[i] + I_[i + 1]
        del I_[i + 1]
        n = sum(map(abs, I_))
        print(n)


### FIXED CODE ###

#!python
# -*- coding: utf-8 -*-

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

a = 0
I = []
for b in A + [0]:
    I.append(b - a)
    a = b
S = sum(map(abs, I))

for i in range(N):
    j = i + 1
    n = S - (abs(I[i]) + abs(I[i + 1])) + abs(I[i] + I[i + 1])
    print(n)
### BUGGY CODE ###

from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in S[::-1]:
  t = int(s)%mod
  r += t*d
  r %= mod
  d *= 10%mod
  p[r] += 1

#p.append(0)
#ans = 0
#c = Counter(p)
#for k,n in c.most_common():
#  if n > 1:
#    ans += 1
#  else:break
  
print(sum([i*(i-1)//2 for i in p]))


### FIXED CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    m = 61
    d = [0]*m
    ans = 0
    for i in range(n):
        ai = a[i]
        for j in range(m):
            if ai&(1<<j):
                ans += (i-d[j])*pow(2,j,mod)%mod
                ans %= mod
                d[j] += 1
            else:
                ans += d[j]*pow(2,j,mod)%mod
                ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    m = 61
    d = [0]*m
    ans = 0
    p = [pow(2,j,mod) for j in range(m)]
    for i in range(n):
        ai = a[i]
        for j in range(m):
            if ai&(1<<j):
                ans += (i-d[j])*p[j]%mod
                ans %= mod
                d[j] += 1
            else:
                ans += d[j]*p[j]%mod
                ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n = int(input())
V = input().split()

def my_sort(d):
    if len(d)==1:
        return list(d.keys())[0], '0', list(d.values())[0], 0
    k_0, k_1, v_0, v_1 = '0', '0', 0, 0
    for k,v in d.items():
        if v_0 < v:
            v_1 = v_0
            k_1 = k_0
            v_0 = v
            k_0 = k
        elif v_1 < v:
            v_1 = v
            k_1 = k
    return k_0, k_1, v_0, v_1


d0, d1 = {}, {}
for i in range(n//2):
    v = V[2*i]
    if v in d0.keys():
        d0[v] += 1
    else:
        d0[v] = 1

    v = V[2*i+1]
    if v in d1.keys():
        d1[v] += 1
    else:
        d1[v] = 1

k0_0, k0_1, v0_0, v0_1 = my_sort(d0)
k1_0, k1_1, v1_0, v1_1 = my_sort(d1)


if k0_0 != k1_0:
    a0 = sum(d0.values()) - v0_0
    a1 = sum(d1.values()) - v1_0
    print(a0 + a1)
else:
    if v0_0 <= v1_0:
        a0 = sum(d0.values()) - v0_1
        a1 = sum(d1.values()) - v1_0
    else:
        a0 = sum(d0.values()) - v0_0
        a1 = sum(d1.values()) - v1_1
    print(a0 + a1)


### FIXED CODE ###

n = int(input())
V = input().split()

d0, d1 = {}, {}
for i in range(n//2):
    v = V[2*i]
    if v in d0:
        d0[v] += 1
    else:
        d0[v] = 1

    v = V[2*i+1]
    if v in d1:
        d1[v] += 1
    else:
        d1[v] = 1

s0 = sorted(d0.items(), key=lambda x: -x[1])
k0_0, v0_0 = s0[0]
s1 = sorted(d1.items(), key=lambda x: -x[1])
k1_0, v1_0 = s1[0]

if k0_0 != k1_0:
    print(n - v0_0 - v1_0)
else:
    k0_1, v0_1 = s0[1] if len(s0)>1 else ('0',0)
    k1_1, v1_1 = s1[1] if len(s1)>1 else ('0',0)
    if v0_0+v1_1 <= v0_1+v1_0:
        print(n - v1_0 - v0_1)
    else:
        print(n - v0_0 - v1_1)
### BUGGY CODE ###

import itertools


X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [a + b for (a, b) in list(itertools.product(A, B))]
AB.sort(reverse=True)
ans = [ab + c for (ab, c) in list(itertools.product(AB[:min(3000, X*Y*Z)], C))]
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

from heapq import heapify, heappop, heappush, heappushpop
 
 
class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)
 
    def push(self, item):
        heappush(self.heap, item)
 
    def pop(self):
        return heappop(self.heap)
 
    def pushpop(self, item):
        return heappushpop(self.heap, item)
 
    def __call__(self):
        return self.heap
 
 
heap = []  # ヒープといっても順序を工夫したただのリスト
 
q = PriorityQueue(heap)
q.push((-(A[0] + B[0] + C[0]), 0, 0, 0))
 
considered = set()
ans = []
for k_th in range(1, K+1):
    heap_max, i, j, k = q.pop()
    ans.append(-heap_max)
    for di, dj, dk in zip([1, 0, 0], [0, 1, 0], [0, 0, 1]):
        i_new, j_new, k_new = i + di, j + dj, k + dk
        if i_new >= X or j_new >= Y or k_new >= Z:
            continue
        if (i_new, j_new, k_new) in considered:
            continue
        considered.add((i_new, j_new, k_new))
        q.push((-(A[i_new] + B[j_new] + C[k_new]), i_new, j_new, k_new))
 
 
print(*ans, sep='\n')
### BUGGY CODE ###

import math
import copy

MOD = 998244353

n = int(input())
xs = []
total = 0
for _ in range(n):
    t = int(input())
    xs.append(t)
    total += t

dp = [[0] * (total+1) for _ in range(n)]

dp[0][0] = 2
dp[0][xs[0]] = 1

for i in range(1,n): # length of
    s = xs[i]
    for j in range (0,total+1):
        dp[i][j] = (dp[i-1][j] * 2) % MOD
        if j - s >= 0:
            dp[i][j] = (dp[i][j] + dp[i-1][j-s]) % MOD

plus = 0
if total % 2 == 0:
    dp2 = [0] * (total // 2 + 1)
    dp2[0] = 1
    intotal = 0
    for i in range(n):
        s = xs[i]
        prev = copy.copy(dp2)
        for j in range(0,len(dp2)):
            if j-s >= 0:
                dp2[j] =  (dp2[j] + prev[j-s]) % MOD
                #print(i,j,s,dp2)
    plus = dp2[total//2]

#print(dp2)
minus = 0
for i in range(math.ceil(total/2), total+1):
    minus = (minus + dp[n-1][i]) % MOD


#print(3**n, minus, plus)
print(((3**n)%MOD - minus*3 + plus*3) % MOD)


### FIXED CODE ###

import math
import copy
import numpy as np

MOD = 998244353

n = int(input())
xxs = []
total = 0
for _ in range(n):
    t = int(input())
    xxs.append(t)
    total += t

xs = np.array(xxs)
dp = np.array([[0] * (total+1) for _ in range(n)])

dp[0][0] = 2
dp[0][xs[0]] = 1

curtotal = xs[0]
for i in range(1,n): # length of
    s = xs[i]
    curtotal += s
    dp[i] = (dp[i-1] * 2)
    dp[i][s:] += dp[i-1][:-s]
    dp[i] %= MOD

#print(dp)

plus = 0
if total % 2 == 0:
    dp2 = np.array([0] * (total // 2 + 1))
    dp2[0] = 1
    curtotal = 0
    for i in range(n):
        s = xs[i]
        curtotal += s
        prev = copy.copy(dp2)
        dp2[s:] += prev[:-s]
        dp2 %= MOD
    plus = dp2[total//2]

#print(dp2)
minus = 0
for i in range(math.ceil(total/2), total+1):
    minus = (minus + dp[n-1][i]) % MOD


#print(3**n, minus, plus)
print(((3**n)%MOD - minus*3 + plus*3) % MOD)
### BUGGY CODE ###

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

for i in range(n-1):
  for j in range(i+1, n):
    SUM += a[j]
  ans += a[i]*SUM
  SUM = 0

print(ans % (10**9 + 7))


### FIXED CODE ###

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

for i in range(n-1):
    a.append(a[i] + A[i])
for i in range(n):
    ans += A[i]*a[i]
print(ans % (10**9 + 7))
### BUGGY CODE ###

h,w = map(int,input().split())
L = []
for i in range(h):
  L.append(tuple(input()))
B = []
W = []
for i in range(h):
  for j in range(w):
    if L[i][j] == '.':
      W.append((i,j))
    else:
      B.append((i,j))
anslist = []
for i in range(len(W)):
  ans = float('inf')
  for j in range(len(B)):
    if ans >= abs(W[i][0]-B[j][0])+abs(W[i][1]-B[j][1]):
      ans = abs(W[i][0]-B[j][0])+abs(W[i][1]-B[j][1])
  anslist.append(ans)
if len(anslist) != 0:
  print(max(anslist))
else:
  print(0)

### FIXED CODE ###

import collections
h,w = map(int,input().split())
q = collections.deque()
A = []
for i in range(h):
    s = input()
    L = []
    for j in range(w):
        if s[j] == '.':
            L.append(s[j])
        else:
            L.append(0)
            q.append([i,j])
    A.append(L)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    cur = q.popleft()
    for i in range(4):
        y = cur[0]+dy_dx[i][0]
        x = cur[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if A[y][x] == '.':
                A[y][x] = A[cur[0]][cur[1]]+1
                q.append([y,x])
ans = 0
for i in range(h):
    for j in range(w):
        if ans < A[i][j]:
            ans = A[i][j]
print(ans)
### BUGGY CODE ###

import sys

H,W=map(int,next(sys.stdin).split())

xs=[[0]*(W) for _ in range(H)]
ys=[[0]*(W) for _ in range(H)]

for i,ln in enumerate(sys.stdin):
    for j,c in enumerate(ln):
        if c!='.':
            continue
        if j==0:
            xs[i][j]=1
        else:
            xs[i][j]+=1+xs[i][j-1]
        if i==0:
            ys[i][j]=1
        else:
            ys[i][j]+=1+ys[i-1][j]
        


#from pprint import pprint
#pprint(xs,width=60)
#print()
#pprint(ys,width=60)

ans=0
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if xs[i][j]==0:
            continue

        if j+1<W and xs[i][j+1]:
            x=xs[i][j]=xs[i][j+1]
        else:
            x=xs[i][j]

        if i+1<H and ys[i+1][j]:
            y=ys[i][j]=ys[i+1][j]
        else:
            y=ys[i][j]

        if x+y-1>ans:
            ans=x+y-1

print(ans)


### FIXED CODE ###

import sys

H,W=map(int,next(sys.stdin).split())

xs=[[0]*(W+2) for _ in range(H+2)]
ys=[[0]*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    row=next(sys.stdin)
    for j in range(1,W+1):
        if row[j-1]!='.': continue
        xs[i][j]=1+xs[i][j-1]
        ys[i][j]=1+ys[i-1][j]

ans=0
for i in range(H,0,-1):
    for j in range(W,0,-1):
        if xs[i][j]==0: continue
        x=xs[i][j]=max(xs[i][j],xs[i][j+1])
        y=ys[i][j]=max(ys[i][j],ys[i+1][j])
        ans=max(ans,x+y-1)

print(ans)