Harryxun/stf_run huggingface dataset:
MOD = 10 ** 9 + 7
n = int(input())


dp = [-1] * (n + 1)
dp[0] = 1
def cnt(num):
    ans = 0
    if num < 0:
        return 1
    if dp[num] != -1:
        return dp[num]
    if num == 1:
        dp[num] = n
        return n
      
    for i in range(n):
        if i == 0:
            ans += cnt(num - 1)
            ans %= MOD
        else:
            ans += cnt(num - 2 - i)
            ans += n - 1
            ans %= MOD
    dp[num] = ans
    return ans

dp[0] = 1
print(cnt(n))

### FIXED CODE ###

MOD = 10 ** 9 + 7
n = int(input())

"""
dp = [-1] * (n + 1)
dp[0] = 1
def cnt(num):
    ans = 0
    if num < 0:
        return 1
    if dp[num] != -1:
        return dp[num]
    if num == 1:
        dp[num] = n
        return n
      
    for i in range(n):
        if i == 0:
            ans += cnt(num - 1)
            ans %= MOD
        else:
            if num - 2 - i < 0:
                ans += 1
            else:
                ans += cnt(num - 2 - i)
            ans += n - 1
            ans %= MOD
    dp[num] = ans
    return ans

dp[0] = 1
print(cnt(n))
"""

dq = [0] * (n + 1)
sum_ = [0] * (n + 1)
dq[0] = 1
sum_[0] = 1
for i in range(n):
    if i == 0:
        dq[i + 1] = n
        sum_[i + 1] = sum_[i] + dq[i + 1]
        continue
    """
    for j in range(n):
        if j == 0:
            dq[i + 1] += dq[i]
        else:
            if i - 1 - j < 0:
                dq[i + 1] += 1
            else:
                dq[i + 1] += dq[i - 1 - j]
            dq[i + 1] += n - 1
    """
    dq[i + 1] += dq[i]
    dq[i + 1] += (n - 1) * (n - 1)
    dq[i + 1] += sum_[i - 2]
    dq[i + 1] += abs(i - n)
    dq[i + 1] %= MOD
    sum_[i + 1] = sum_[i] + dq[i + 1]
    sum_[i + 1] %= MOD

print(dq[-1])
# coding=utf-8

if __name__ == "__main__:
    S = input()

    if S == "Sunny":
        print("Cloudy")
    elif S == "Cloudy":
        print("rainy")
    else:
        print("Sunny")


### FIXED CODE ###

# coding=utf-8

if __name__ == "__main__":
    S = input()

    if S == "Sunny":
        print("Cloudy")
    elif S == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
s=list(input())

a=s.index("A")
for i in range(len(s),0):
  if s[i-1]=="Z":
    z=i-1
z-=len(s)-1
sum=z-a+1
print(sum)

### FIXED CODE ###

s=list(input())
n=len(s)
a=s.index("A")
for i in range(n,0,-1):
  if s[i-1]=='Z':
    z=i
    break
sum=z-a
print(sum)
n,k=int(input()),int(input())
a=list(map(int,input().split()))
s=set(a)
if len(s)<=k:
    print(0)
else:
    print(len(s)-k)


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
s=[0 for i in range(n)]
z=set(a)
y=len(z)
for x in a:
    s[x-1]+=1
b=sorted(s)
f=0
ans=0
for x in b:
    if x!=0:
        f+=1
        ans+=x
    if f>=y-k:
      	break
print(ans)
A, B = map(int, input().split())

max_num = max(A, B)
target = list(range(2, max_num + 1))
primes = set()
while True:
    num = min(target)

    if num * num > max_num:
        break

    primes.add(num)

    i = 0
    while i < len(target):
        if target[i] % num == 0:
            target.pop(i)
            continue
        i += 1

count = 1
for prime in primes:
    if A % prime == 0 and B % prime == 0:
        count += 1
print(count)

### FIXED CODE ###

def prime_facorize(N):
    res = {1}
    for i in range(2, int(N ** 0.5) + 1):
        while N % i == 0:
            res.add(i)
            N /= i

        if N <= 1:
            break
    if N > 1:
        res.add(N)
    return res


A, B = map(int, input().split())
commons = prime_facorize(A) & prime_facorize(B)
print(len(commons))
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


N = int(input())
A = list(map(int, input().split()))
# gcd_list = []
# hoge = gcd(A[0], A[1])
# for i in range(2, N):
#     gcd_list.append(gcd(hoge, A[i]))
# gcd_list.sort()
# print(gcd_list[len(gcd_list)-2])
A.sort()
max_A = max(A)
gcd_list = []
for i in range(int(N/2):
    tmp = A[i]
    A[i] = max_A
    hoge = gcd(A[0], A[1])
    for j in range(2, int(N/2):
        hoge = gcd(A[j], hoge)
    gcd_list.append(hoge)
    A[i] = tmp

print(max(gcd_list))
# 最大の値と変えてもいい


### FIXED CODE ###

def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


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

left = [0]
right = [0]

for i in range(N):
    left.append(gcd(left[-1], A[i]))
    right.append(gcd(right[-1], A[(N-1)-i]))  # こっちのAは後ろからみる, iがN-1になった時はA[0]


right.reverse()  # indexが小さいほうが多くの数字を考慮した最大公約数になっている


gcd_list = [gcd(left[i], right[i+1]) for i in range(N)]

print(max(gcd_list))
s=input()
num0,num1=0,0
for i in s:
  if i=='0':
    nums0+=1
  elif i=='1':
    nums1+=1
print(2*min(num0,num1))

### FIXED CODE ###

s=input()
a_1=s.count("1")
b_1=s.count("0")
if a_1<=b_1:
  print(2*a_1)
else:
  print(2*b_1)
import math

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

lst = []
for i in range(1,math.gcd(A, B)+1):
    if A % i == 0 and B % i == 0:
        lst.append(i)

if len(lst) == 1:
    print(1)
else:
    check = [lst[1]]
    for i in range(1, len(lst)):
        for c in check:
            if lst[i] % c == 0:
                break
        else:
            check.append(lst[i])
    print(len(check)+1)


### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    return divisors

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

listA = make_divisors(A)
listB = make_divisors(B)
lst = list(set(listA) & set(listB))

lst.sort()

if len(lst) == 1:
    print(1)
else:
    check = [lst[1]]
    for i in range(1, len(lst)):
        for c in check:
            if lst[i] % c == 0:
                break
        else:
            check.append(lst[i])
    print(len(check)+1)
import math
A, B, H, M = map(int, input().split())
 
t = (H + (M / 60)) * math.pi / 6
m = (M / 60) * 2 *math.pi
totalangle = m - t
result = sqrt(A ** 2 + B ** 2 - 2 * A * B *math.cos(totalangle))
print(result)

### FIXED CODE ###

import math
 
A, B, H, M = map(int, input().split())
 
m = (M / 60) * 2 * math.pi
t = (H + (M / 60)) * math.pi / 6
angle = m-t
res = math.sqrt(A ** 2 + B ** 2 - 2 * A * B * math.cos(angle))
print(res)
atcoder beginner contest

### FIXED CODE ###

x, y, z = input().split()
print(x[0].upper()+y[0].upper()+z[0].upper())
a,b,c = map(int,input().split())
if a==b+c or b==a+c or c==a+b :print('Yes')
  else:print('No')


### FIXED CODE ###

a,b,c = list(map(int,input().split()))
if a==b+c or b==a+c or c==a+b :print('Yes')
else:print('No')
A,B,K = map(int,input().split())

i=0
j=1
while i<K:
  if A%j=0^B%j=0:
     i +=1
  else:
     i =i
  j+=1

print(j)
  

### FIXED CODE ###

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

i=0
j=100
while i<K:
    if A%j==0 and B%j==0:
        i +=1
    else:
        i =i
    j-=1

print(j+1)
import sys
N = int(input())

if N > 81:
    print('No')
else:
    val = []
    i = 3
    while N != 1:
        if N % 2 == 0:
            val.append(2)
            N //= 2
        else:
            if i >= 10:
                print('No')
                sys.exit()
            elif N % i == 0:
                val.append(i)
                N //= i
            else:
                i += 2
if val.count(5) >= 2 and len(val) >= 3:
    print('No')
elif val.count(7) >= 2 and len(val) >= 3:
    print('No')
else:
    print('Yes')
        


### FIXED CODE ###

import sys
N = int(input())

if N > 81 or N == 50 or N == 60 or N == 70 or N == 80:
    print('No')
    sys.exit()
else:
    val = []
    i = 3
    while N != 1:
        if N % 2 == 0:
            val.append(2)
            N //= 2
        else:
            if i >= 10:
                print('No')
                sys.exit()
            elif N % i == 0:
                val.append(i)
                N //= i
            else:
                i += 2

print('Yes')
n = int(input())

if n == 1:
    print(1)
else:
    for x in range(1,n):
        tmp = (1+x)*x//2
        if tmp >= n:
            l = x
            break

    d = tmp - n
    for x in range(1,l+1):
        if x != d:
            print(x)

### FIXED CODE ###

n = int(input())

if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    for x in range(1,n):
        tmp = (1+x)*x//2
        if tmp >= n:
            l = x
            break

    d = tmp - n
    for x in range(1,l+1):
        if x != d:
            print(x)
print('a' if s.islower() else 'A')

### FIXED CODE ###

s=input()
print('a' if s.islower() else 'A')
S = input()
x == ARC
if S == ARC:
  x == ABC
print(x)

### FIXED CODE ###

S = input()
x = "ARC"
if S == "ARC":
  x = "ABC"
print(x)
for I in range(0, 9)
 for j in range(0, 9)
  print(str(I) + "*" + str(j) + "=" + str(I * j))


### FIXED CODE ###

def multi():
    for i in range(1, 10):
        for j in range(1, 10):
            print(str(i) + "x" + str(j) + "=" + str(i * j))

if __name__ == '__main__':
    multi()
N, X = map(int, input().split())
x = list(map(int, input().split()))

is_ok = True
# x[i] - X たちの最大公約数

from math import gcd
if N == 1:
    print(abs(x[0]-X))
elif N == 2:
    GCD = gcd(abs(x[0]-X), abs(x[1]-X))
    print(GCD)
else:
    GCD = gcd(abs(x[0]-X), abs(x[1]-X))
    for i in range(2, N):
        a = abs(x[i] - X)
        GCD = gcd(GCD, a)

    print(GCD)

### FIXED CODE ###

N, X = map(int, input().split())
x = list(map(int, input().split()))

is_ok = True
# x[i] - X たちの最大公約数

from fractions import gcd
if N == 1:
    print(abs(x[0]-X))
elif N == 2:
    GCD = gcd(abs(x[0]-X), abs(x[1]-X))
    print(GCD)
else:
    GCD = gcd(abs(x[0]-X), abs(x[1]-X))
    for i in range(2, N):
        a = abs(x[i] - X)
        GCD = gcd(GCD, a)

    print(GCD)
x, y = int(input())
print(x/y)

### FIXED CODE ###

x,y = map(int,input().split())
print(x/y)
if (n = input().split())[0] == n[2] : print('Yes')
else : print('No')


### FIXED CODE ###

n = input()
if n[0] == n[2] : print('Yes')
else : print('No')
n,k=map(int,input().split())
l=[]
for j in range(0,n):
    l.append(input().split())
ans=0
for a in range(0,k):
     for b in range(0,a+1):
         i=0
         total=0
         while i<n:
           m=((int(l[i][0])-a)//k)%2
           h=((int(l[i][1])-b)//k)%2
           if ((m+h)%2==0 and str(l[i][2])=="W") or ((m+h)%2==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2==0:
     print('Even')
else:
     print("Odd")
a,b=map(int,input().split())
if (a*b)%2!==0:
  print("Yes")
elif (a*b*3)%2!==0:
  print("Yes")
  
else:
  print("No)

### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2!=0:
  print("Yes")
elif (a*b*3)%2!=0:
  print("Yes")
  
else:
  print("No")
a, b = map(int, input())


print(min( 0, a - 2 * b ))
  

### FIXED CODE ###

a, b = map( int, input().split())
print( max( 0, a - b * 2 ))
N = int(input())
a = [input() for i in range(N)]
 
for num in range(N):
  if a[num] in a[:num]:
    print('No')
    break
  if num < N-1:
    if a[num][-1] != a[num+1][0]:
    	print('No')
    	break
  print('Yes')

### FIXED CODE ###

A, B = map(int, input().split())
x = A * B
if x % 2 == 0:
    print('No')
else:
    print('Yes')
n=int(input())
a=[map(int,input().split())]
a.sort(reverse=True)
print(sum(a[::2]-a[1::2])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
print(sum(a[::2])-sum(a[1::2]))
n = int(input())
m = int(input())

if n == 1:
    n = 14
if m == 1:
    m = 14

if n > m:
    print("Alice")
elif m > n:
    print("Bob")
else:
    print("Draw")




### FIXED CODE ###

l1 = input().split()
a = int(l1[0])
b = int(l1[1])
if a == b:
    print("Draw")
    exit()
if a == 1:
    print("Alice")
    exit()
if b ==1:
    print("Bob")
    exit()
if a > b:
    print("Alice")
if b > a :
    print("Bob")
a, b, c = [int(i) for i in input()].split()]

count = 0

for i in range(a, b + 1):
    if c % 1 ==0:
        count += 1
print(count)

### FIXED CODE ###

a, b, c = [int(i) for i in input().split()]
 
total = 0
for d in range(a, b + 1):
    if c % d == 0:
        total += 1
 
print(total)
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

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

max_ans = 0
for i in range(len(A)):
    tmp = A[:i] + A[1+i:]
    ans = gcd_list(tmp)
    if max_ans < ans:
        max_ans = ans
print(max_ans)

### FIXED CODE ###

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a


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

# 累積最大公約数的な
head = []
tail = []
head.append(A[0])
tail.append(A[-1])
for i, j in zip(A[1:], A[N-2::-1]):
    head.append(gcd(head[-1], i))
    tail.append(gcd(tail[-1], j))
ans = 0
for i in range(len(head)-2):
    tmp = gcd(head[i], tail[len(tail)-1-2-i])
    if ans < tmp:
        ans = tmp
print(max(head[-1], head[-2], tail[-2], ans))
lista=[]
soma=[]
for x in input().split():
    lista.append(int(x))
for var1 in lista:
    for var2 in lista:
        if var1!=var2:
            soma.append(var1+var2)

min=min(soma)
print(min)


### FIXED CODE ###

x = input().split()
P = int(x[0])
Q = int(x[1])
R = int(x[2])
l = [P+Q,Q+R,R+P]
print(min(l))
N = int(input())
a = list(map(int,input().split()))

def solve(l, K=0):
  if K+1 in l:
    pos = l.index(K+1)
    return solve(l[pos:],K+1)
  else:
    return K
  
def judge(x):
  if x == 0:
    return -1
  else:
    return N-x


print(judge(solve(a)))


### FIXED CODE ###

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

counter = 0
for i in range(N):
  if a[i] == counter+1:
    counter += 1

ans = -1 if counter == 0 else N - counter
print(ans)
a=input()
b=input()
print((a*b) 2*(a+b))

### FIXED CODE ###

a,b = map(int, raw_input().split())
print a*b,(a+b)*2
N = int(input())
S = input()

count = 0
for i in range(N-3):
  if S[i]S[i+1]S[i+2] == ABC:
    count = +1
  else:
    continue
print(count)

### FIXED CODE ###

N = int(input())
S = input()

count = 0
for i in range(N-2):
  if S[i]+S[i+1]+S[i+2] == "ABC":
    count += 1
  else:
    continue
    
print(count)
def dfs(s, to, color, palette, i=0):
    seen[s] = 1
    for v in to[s]:
        if seen[v]:
            continue
        if s < v:
            color[sides.index([s, v])] = palette[i % len(palette)]
            i += 1
        dfs(v, to, color, palette, i)


N = int(input())
sides = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(N - 1)]
to = [[] for _ in range(N)]
for a, b in sides:
    to[a].append(b)
    to[b].append(a)

colors_used = max(len(sub) for sub in to)
palette = [i for i in range(1, colors_used+1)]
seen = [0] * N
color = [0] * (N - 1)

dfs(0, to, color, palette)

print(colors_used)
print(*color, sep='\n')

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**9)


N = int(input())
to = [[] for _ in range(N)]
order = []

for _ in range(N - 1):
    a, b = list(map(lambda x:int(x) - 1, input().split()))
    to[a].append(b)
    to[b].append(a)
    order.append(b)


def solve():
    dist = [-1] * N
    # 頂点iに向かう辺をiとする
    color = [0] * N
    dist[0] = 0
    color[0] = 0
    que = deque([0])

    while que:
        v = que.popleft()
        used_color = [color[v]]
        next_color = 1
        for nv in to[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                while next_color in used_color:
                    next_color += 1
                color[nv] = next_color
                used_color.append(next_color)
                que.append(nv)

    print(len(set(color[1:])))
    for i in range(N - 1):
        print(color[order[i]])


if __name__ == "__main__":
    solve()
import queue
h,w,n = map(int,input().split())
factrys = [None] * (n + 1)
ss = ["X" * (w + 2)]
for i in range(h):
  s = "X" + input() + "X"
  if "S" in s:
    factrys[0] = (i + 1, s.index("S"))
  for j in range(1,n + 1):
    if str(j) in s:
      factrys[j] = (i + 1, s.index(str(j)))
  ss.append(s)
ss.append("X" * (w + 2))
mp = []
que = queue.Queue()
def bfs(i):
  while True:
    (x,y) = que.get()
  #  print(i,x,y)
  #  print(mp[x][y])
    if (x,y) == factrys[i + 1]:
      return mp[x][y]
    count = mp[x][y]
    if ss[x + 1][y] != "X" and mp[x + 1][y] is None:
      mp[x + 1][y] = count + 1
      que.put((x + 1, y))
    if ss[x - 1][y] != "X" and mp[x - 1][y] is None:
      mp[x - 1][y] = count + 1
      que.put((x - 1, y))
    if ss[x][y + 1] != "X" and mp[x][y + 1] is None:
      mp[x][y + 1] = count + 1
      que.put((x, y + 1))
    if ss[x][y - 1] != "X" and mp[x][y - 1] is None:
      mp[x][y - 1] = count + 1
      que.put((x, y - 1))

def bfs_(i):
  for count in range(1000000):
    sz = que.qsize()
    for loop in range(sz):
      (x,y) = que.get()
      if ss[x][y] == "X" or not mp[x][y] is None:
        continue
      if (x,y) == factrys[i + 1]:
        return count
      mp[x][y] = count
      que.put((x + 1, y))
      que.put((x - 1, y))
      que.put((x, y - 1))
      que.put((x, y + 1))

ans = 0
for i in range(n):
  mp = [[None] * (h + 2) for j in range(w + 2)]
  x,y = factrys[i]
  que = queue.Queue()]
  mp[x][y] = 0
  que.put((x,y))
  ans += (bfs(i))
print(ans)


### FIXED CODE ###

from collections import deque

def main():
  h, w, n = map(int, input().split())
  mp = ["X" + input() + "X" for _ in range(h)]
  mp.insert(0, "X" * (w + 2))
  mp.append("X" * (w + 2))
  
  poss = [None] * (n + 1)
  for y in range(1, h + 1):
    for x in range(1, w + 1):
      if mp[y][x] == "S":
        poss[0] = (x, y)
      elif "1" <= mp[y][x] <= "9":
        poss[int(mp[y][x])] = (x, y)
  
  ans = 0
  vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
  for i in range(n):
    sx, sy = poss[i]
    gx, gy = poss[i + 1]
    used = [[False] * (w + 2) for _ in range(h + 2)]
    used[sy][sx] = True
    que = deque()
    push = que.append
    pop = que.popleft
    push((0, sx, sy))
    while que:
      cnt, x, y = pop()
      if (x, y) == (gx, gy):
        ans += cnt
        break
      
      for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if used[ny][nx] or mp[ny][nx] == "X":continue
        used[ny][nx] = True
        push((cnt + 1, nx, ny))
  
  print(ans)

main()
def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    
    points = []
    for i in range(N):
        x, y = map(int, f_i.readline().split())
        points.append(x + y * 1j)
    
    radiuses = []
    from itertools import combinations
    for p1, p2 in combinations(points, 2):
        c = (p1 + p2) / 2
        r = max(abs(p1 - c), abs(p2 - c))
        for p in points:
            if abs(p - c) > r:
                break
        else:
            radiuses.append(r)
    
    print(min(radiuses))

solve()

### FIXED CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    
    points = []
    for i in range(N):
        x, y = map(int, f_i.readline().split())
        points.append(x + y * 1j)
    
    from itertools import combinations
    radiuses = []
    
    for p1, p2 in combinations(points, 2):
        c = (p1 + p2) / 2
        r = abs(p1 - c)
        for p in points:
            if abs(p - c) > r:
                break
        else:
            radiuses.append(r)
    
    if radiuses:
        return min(radiuses)
    
    def circumcircle(a, b, c):
        n = (a - b) * abs(c) ** 2 + (b - c) * abs(a) ** 2 + (c - a) * abs(b) ** 2
        d = (a - b) * c.conjugate() + (b - c) * a.conjugate() + (c - a) * b.conjugate()
        return n / d # center of circumcircle
    
    err = 10 ** -7
    for p1, p2, p3 in combinations(points, 3):
        z1 = p3 - p1
        z2 = p2 - p1
        if z1.real * z2.imag == z1.imag * z2.real:
            continue
        
        c = circumcircle(p1, p2, p3)
        r = abs(p1 - c)
        for p in points:
            #if abs(p - c) > r:
            if abs(p - c) - r > err:
                break
        else:
            radiuses.append(r)
    
    return min(radiuses)

print(solve())
s = input()

if s[2] == a[3] and s[4] == s[5]:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

s = input()

if s[2] == s[3] and s[4] == s[5]:
    print("Yes")
else:
    print("No")
data = input().split()
a = data[0]
b = data[1]
print(int(a) * int(b))
print(2 * (int(a) + int(b))


### FIXED CODE ###

data = input().split()
a = data[0]
b = data[1]
print(int(a) * int(b), 2 * (int(a) + int(b)))
# coding:utf-8

import bisect

INF = float('inf')
MOD = 10 ** 9 + 7


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


def solve(num_cnt: list) -> int:
    num_cnt.sort()
    t = 2 ** (len(bin(num_cnt[-1])) - 2)
    used = [False] * len(num_cnt)
    cnt = 0
    for i in range(len(num_cnt))[::-1]:
        if used[i]:
            continue
        n = num_cnt[i]
        used[i] = True
        while 2 * n < t:
            t //= 2
        j = bisect.bisect_left(num_cnt, t - n)
        # print(n, t, j)
        if t - n == num_cnt[j] and n != t - n:
            cnt += 1
            used[j] = True

    return cnt


N = int(input())
A = inpl()

cnt_e, cnt_o = [], []
for a in A:
    if a % 2:
        cnt_o.append(a)
    else:
        cnt_e.append(a)

print(solve(cnt_e) + solve(cnt_o))


### FIXED CODE ###

# coding:utf-8

import sys
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    A = LI()

    MA = defaultdict(int)
    # 目標値をO(1)で見つけるために辞書に格納
    for a in A:
        MA[a] += 1

    key_n = list(MA.keys())
    key_n.sort()
    key_n.reverse()

    res = 0
    p = 30
    for x in key_n:
        # すでにペアを作るために使用してしまっている時はパス
        if not MA[x]:
            continue

        # 残っているボールの中で一番大きな値xを選ぶと，そのボールを使って表せる2べきの値x + yは1つに定まる
        # x + 1 <= x + y < 2x
        # 2べきの比は2であるのに対して，x + 1と2xの比は2未満だから
        while 2 * x < 2 ** p:
            p -= 1

        if x + 1 <= 2 ** p:
            y = 2 ** p - x
            if not MA[y]:
                continue

            if x == y:
                _add = MA[x] // 2
            else:
                _add = min(MA[x], MA[y])

            res += _add
            MA[x] -= _add
            MA[y] -= _add

    print(res)


if __name__ == '__main__':
    main()