Harryxun/stf_run huggingface dataset:
N = int(input())
A = list(map(int, input().split()))
ans = 1
b = 1
c = 1
p = 10**18
    
for i in range(N):
  elif A[i] == 0:
    c = 0
    break
  else:
    ans *= A[i]
    if p < ans:
      b = -1
      ans = 0
if c == 0:
  print(c)
elif b == -1:
  print(b)
else:
  print(ans)
    
  

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
n0 = A.count(0)
n1 = A.count(1)
import math
ans = 1
if N-n0-n1>60:
  ans = -1
for i in range(N):
  if A[i] == 0 or ans == 0:
    ans = 0
    break
  elif ans <0:
    ans = -1
  elif math.log10(A[i])+math.log10(ans)>18:
    ans = -1
    b = 1
  else:
    ans *= A[i]

if ans == 0:
  print(0)
elif ans < 0:
  print(-1)
elif ans>10**18:
  print(-1)
else:
  print(ans)
def base_convert(nl, ibase, obase):
    o = []
    while any(nl):
        c = 0
        for i in range(len(nl)):
            c = c * ibase + nl[i]
            nl[i],c = divmod(c,obase)
        o.append(c)
    o.reverse()
    return o

def convertList(lst):
    rev_lst = list(reversed(lst))
    for i,num in enumerate(rev_lst):
        if i < len(rev_lst)-1:
            if num <= 0:
                rev_lst[i+1] = rev_lst[i+1]-1
                rev_lst[i] = rev_lst[i] + 26
    return list(reversed(rev_lst))

N = input()
N = list(map(int,[i for i in N]))
lst = base_convert(N,10,26)
lst_converted = convertList(lst)
ans = ''.join([dict1[i] for i in lst_converted])
print(ans)

### FIXED CODE ###

def base_convert(nl, ibase, obase):
    o = []
    while any(nl):
        c = 0
        for i in range(len(nl)):
            c = c * ibase + nl[i]
            nl[i],c = divmod(c,obase)
        o.append(c)
    o.reverse()
    return o

def convertList(lst):
    rev_lst = list(reversed(lst))
    for i,num in enumerate(rev_lst):
        if i < len(rev_lst)-1:
            if num <= 0:
                rev_lst[i+1] = rev_lst[i+1]-1
                rev_lst[i] = rev_lst[i] + 26
    return list(reversed(rev_lst))

dict1 = {
    0: '',
    1: 'a',
    2: 'b',
    3: 'c',
    4: 'd',
    5: 'e',
    6: 'f',
    7: 'g',
    8: 'h',
    9: 'i',
    10: 'j',
    11: 'k',
    12: 'l',
    13: 'm',
    14: 'n',
    15: 'o',
    16: 'p',
    17: 'q',
    18: 'r',
    19: 's',
    20: 't',
    21: 'u',
    22: 'v',
    23: 'w',
    24: 'x',
    25: 'y',
    26: 'z'
}

N = input()
N = list(map(int,[i for i in N]))
lst = base_convert(N,10,26)
lst_converted = convertList(lst)
ans = ''.join([dict1[i] for i in lst_converted])
print(ans)
X,Y,A,B,C = [int(x) for x in input().split()]
R = [int(x) for x in input().split()]
G = [int(x) for x in input().split()]
CL = [int(x) for x in input().split()]

dp = [[0]*(X+1) for d in range(Y+1)]
for i in range(X):
    for j in range(Y):
        MAX = max(max(R[j],CL[j]),max(G[i],CL[i]))
        dp[i][j] = MAX
        if MAX == R[j]:
            A.pop(0)
        elif MAX == G[i]:
            B.pop(0)
        else:
            C.pop(0)

print(dp[-1])

### FIXED CODE ###

X,Y,A,B,C = [int(x) for x in input().split()]
R = sorted([int(x) for x in input().split()],reverse = True)[:X]
G = sorted([int(x) for x in input().split()],reverse = True)[:Y]
CL = sorted([int(x) for x in input().split()],reverse = True)[:X+Y]
total = sorted(R+G+CL, reverse=True)[:X+Y]
print(sum(total))
n , m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = []
for i in range(m):
    b, c = map(int, input().split())
    bc.append([b,c])
bc.sort(key = lambda x : -x[1])
box = []
for b, c in bc:
    box.extend([c]*b)

k = 0
for b , c in bc:
    for i in range(k ,min( k + b, n)):
        A[i] = max(A[i] , c)
    k += b

print(sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))

bc = []
for i in range(m):
    b, c = map(int, input().split())
    bc.append([b,c])

from operator import itemgetter
bc.sort(key=itemgetter(1), reverse = True)
k = 0
c = bc[0][1]
b = bc[0][0]
bn = 0
while A[k] < c:
    A[k]=c
    k+=1
    if k == len(A):
        break
    b-=1
    if b  == 0:
        bn += 1
        if bn == len(bc):
            break
        b = bc[bn][0]
        c = bc[bn][1]
print(sum(A))
# -*- coding: utf-8 -*-

def main():
    N=int(input())  #数値入力 「N」だけの入力のとき
    H=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
    D=list()
    g = 0
    for i in range(1, N):
        if H[i-1] >= H[i]:
            g += 1
            if i == N-1:
                D.append(g)
        else:
            D.append(g)
            g = 0
    #print("D")
    #print(D)

    print(max(D))

if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())
H = [int(x) for x in input().split()]
ans = 0
cnt = 0
for ind,i in enumerate(H[:-1]):
    if(i>=H[ind+1]):
        cnt += 1
    else:
        cnt = 0
    ans = max(ans,cnt)
print(ans)
mod = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= mod
        return ans

    neg = []
    pos = []
    for a in A:
        if a > 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)
    if K > len(pos) + len(neg):
        return 0
    pos.sort()
    neg.sort(reverse=True)

    if len(neg) == N:
        res = 1
        for i in range(K):
            res *= neg[i]
            res %= mod
        return res

    ans = 1

    if K & 1:
        ans *= pos.pop()
        K -= 1
    # この時点でKは偶数
    while K > 1 and len(pos) > 1 and len(neg) > 1:
        K -= 2
        if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
            ans *= pos.pop()
            ans *= pos.pop()
            ans %= mod
        else:
            ans *= neg.pop()
            ans *= neg.pop()
            ans %= mod
    while K > 1 and len(pos) > 1:
        K -= 2
        ans *= pos.pop()
        ans %= mod
        ans *= pos.pop()
        ans %= mod
    while K > 1 and len(neg) > 1:
        K -= 2
        ans *= neg.pop()
        ans %= mod
        ans *= neg.pop()
        ans %= mod
    return ans


if __name__ == "__main__":
    print(main())

### FIXED CODE ###

mod = 10 ** 9 + 7

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

neg = []
zero = 0
pos = []
for a in A:
    if a < 0:
        neg.append(a)
    else:
        pos.append(a)

pos.sort()
neg.sort(reverse=True)

if len(pos) == 0:
    res = 1
    if K % 2 == 0:
        neg.reverse()
    for a in neg[:K]:
        res *= a
        res %= mod
else:
    res = 1
    if K % 2 == 1:
        res = pos.pop()
        K -= 1
    while K > 1 and len(pos) > 1 and len(neg) > 1:
        if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
            res *= pos.pop()
            res %= mod
            res *= pos.pop()
            res %= mod
        else:
            res *= neg.pop()
            res %= mod
            res *= neg.pop()
            res %= mod
        K -= 2
    while K > 1 and len(pos) > 1:
        res *= pos.pop()
        res %= mod
        res *= pos.pop()
        res %= mod
        K -= 2
    while K > 1 and len(neg) > 1:
        res *= neg.pop()
        res %= mod
        res *= neg.pop()
        res %= mod
        K -= 2
    while K and pos:
        res *= pos.pop()
        res %= mod
        K -= 1
    while K and neg:
        res *= neg.pop()
        res %= mod
        K -= 1


print(res)
#n = int(input())
#L = list(map(int, input().split()))
import math
import sys
import heapq
import fractions

nCr = {}
def cmb(n, r):
    if r == 0 or r == n:
        return 1
    if r == 1:
        return n
    if (n, r) in nCr:
        return nCr[(n, r)]
    nCr[(n, r)] = cmb(n-1, r) + cmb(n-1, r-1)
    return nCr[(n, r)]

N = int(input())
s = []
n = 0
for i in range(N):
    s.append(list(input()))
ans = 0
s.sort()
for i in range(N):
    s[i]=set(s[i])
for i in range(N-1):
    if s[i]==s[i+1]:
        n += 1
        if i == N-2:
            ans += cmb(n+1, 2)
    else:
        if n > 0:
            ans += cmb(n+1,2)
        n = 0
print(ans)


### FIXED CODE ###

#n = int(input())
#L = list(map(int, input().split()))
import math
import sys
import heapq
import fractions


def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

N = int(input())
s = []
n = 0
for i in range(N):
    s.append(list(input()))
ans = 0


for i in range(N):
    s[i].sort()
s.sort()

for i in range(1,N):

    if s[i]==s[i-1]:
        n += 1
        if i == N-1:
            ans += cmb(n+1, 2)
    else:
        if n > 0:
            ans += cmb(n+1,2)
            n = 0
print(ans)
import sys
import numpy as np

read = sys.stdin.read

n = int(input())
a = np.array(readline().split(), dtype=np.int64)
a.sort()
a = a[::-1]
m = -(-n//2)
ans = np.sum(a[:m])*2 - a[0] if n % 2 == 0 else np.sum(a[:m])*2 - a[0] - a[m]
print(ans)

### FIXED CODE ###

import sys
import numpy as np

readline = sys.stdin.readline
read = sys.stdin.read

n = int(input())
a = np.array(readline().split(), dtype=np.int64)
a.sort()
a = a[::-1]
m = -(-n//2)
ans = np.sum(a[:m])*2 - a[0] if n % 2 == 0 else np.sum(a[:m])*2 - a[0] - a[m-1]
print(ans)
n=int(input())
lst=[]
cnt=0
for i in range(n):
  x=input()
  if i>=1:
    if x in lst:
      print('No')
      cnt+=1
      exit()
    lst+=x
    if lst[i][0]!=lst[i-1][-1]:
      print('No')
      cnt+=1
      exit()
if cnt==0:
  print('Yes')


### FIXED CODE ###

n=int(input())
x=[input() for _ in range(n)]
ans='Yes'
if len(x)==len(set(x)):
  for i in range(n-1):
    if x[i][-1]!=x[i+1][0]:
      ans='No'
      break
else:
  ans='No'
print(ans)
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(1, N+1):
    weight = WV[i-1][0]
    value = WV[i-1][1]
    for w in range(W+1):
        if w-weight<0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w-weight]+value, dp[i-1][w])

print(dp[N][W])


### FIXED CODE ###

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]

dp = [[0]+[float('inf')]*100000 for _ in range(N+1)]

for i in range(1, N+1):
    for v in range(0, 100001):
        weight = WV[i-1][0]
        value = WV[i-1][1]
        dp[i][v] = min(dp[i-1][v], dp[i-1][v-value]+weight)
res = 0
for v, w in enumerate(dp[-1]):
    if w <= W: res = v

print(res)
from math import gcd
n = int(input())
T = [int(input()) for i in range(n)]
ans = 1
for t in T:
    ans = ans*t//gcd(ans,t)
print(ans)

### FIXED CODE ###

from fractions import gcd
n = int(input())
T = [int(input()) for i in range(n)]
ans = 1
for t in T:
    ans = ans*t//gcd(ans,t)
print(ans)
I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################
from collections import defaultdict
tree = defaultdict(list)


def inc(tree,counter,p,x):
    if tree[p] == []:
        return
    for i in tree[p]:
        counter[i-1]+=x
        inc(tree,counter,i,x)

n ,q = I0()
counter = [0]*n
for i in range(n-1):
    a,b=I0()
    tree[a].append(b)


for i in range(q):
    p,x = I0()
    counter[p-1]+=x
    inc(tree,counter,p,x)

print(*counter)



### FIXED CODE ###

I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################


from sys import stdin,setrecursionlimit
#from copy import deepcopy
 
setrecursionlimit(10**6)
input=stdin.readline

def dfs(p,father=-1):
    for i in tree[p]:
        if i == father:
            continue
        counter[i]+=counter[p]
        dfs(i,p)

n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(q):
    p,x = I0()
    counter[p-1]+=x
    

dfs(0)

print(*counter)

'''stack = [1]
while stack:
    yy = stack.pop()
    for i in tree[yy]:
        counter[i-1]+=counter[yy-1]
        stack.append(i)'''
x = input()
print(X**3)


### FIXED CODE ###

x = int(input())
print(x**3)
n,q=map(int,input().split())
s=input()
a=[0]
for l in range(n):
    if s[l]=='A' and s[l+1]=='C':
        for j in range(1,2):
            a.append(a[l]+1)
        l+=1
    else :
        a.append(a[l])
for k in range(q):
    x,y=map(int,input().split())
    print(a[y-1]-a[x-1])
print(a)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0,0]
for l in range(1,n):
    if s[l-1]=='A' and s[l]=='C':
        a.append(a[l]+1)
    else :
        a.append(a[l])
for k in range(q):
    x,y=map(int,input().split())
    print(a[y]-a[x])
n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")

box = [0] * (maxbit + 1)

def f(i):
  cnt = 0
  while i > 0:
    if box[i] != 0:
      return box[i] + cnt
    i %= bin(i).count("1")
    cnt += 1
  return cnt

for i in range(1, min(maxbit + 1, 200000)):
  box[i] = f(i)

for i in range(lenx):
  if x[i] == "0":
    mb = maxbit + 1
    t = x10 + pow(2, (lenx - 1 - i), mb)
  else:
    mb = maxbit - 1
    t = x10 - pow(2, (lenx - 1 - i), mb)
  # print(t, mb)
  if t == 0:
    print(0)
  else:
    t %= mb 
    if t == 0:
      print(1)
    else:
      ans = f(t) + 1 
      box[t] = ans
      print(ans)

### FIXED CODE ###

n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")
xc0 = x10 % (maxbit + 1)
xc1 = x10 % (maxbit - 1) if maxbit > 1 else 0

def f(ii):
  cnt = 0
  while ii > 0:
    ii %= bin(ii).count("1")
    cnt += 1
  return cnt

for i in range(lenx):
  if x[i] == "0":
    t = xc0 + pow(2, (lenx - 1 - i), maxbit + 1)
    ans = f(t % (maxbit + 1)) + 1
  else:
    if maxbit - 1 == 0:
      ans = 0
    else:
      t = xc1 - pow(2, (lenx - 1 - i), maxbit - 1)
      ans = f(t % (maxbit - 1)) + 1
  print(ans)
A, B = map(int, input())

print(max(max(A+B, A - B), A * B))

### FIXED CODE ###

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

print(max(max(A+B, A - B), A * B))
n, k = map(int, input().split())
pos = [int(i) for i in input().split()]
score = [int(i) for i in input().split()]
if max(score) <= 0:
  print(max(score))
else:
  pos = [0] + pos
  score = [0] + score
  max_point = -10 ** 10
  s_l = [[0]]
  nei = {}
  dic = {}
  loop = 0
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    points = [0]
    count = 0
    if f_pos not in nei:
      loop += 1
      while True:
        n_pos = pos[f_pos]
        points.append(points[-1] + score[n_pos])
        count += 1
        nei[f_pos] = [count, loop]
        if n_pos in nei:
          dic[loop] = count
          break
        f_pos = n_pos
      #print(points)
      #print(nei)
      s_l.append(points)
      loop_num = count
      count = 1
    else:
      loop = nei[f_pos][1]
      count = nei[f_pos][0]
      loop_num = dic[loop]
      points = s_l[loop]
    s = points[count - 1]
    m = points[loop_num] - s
    a = k // loop_num
    b = k % loop_num
    if points[loop_num] > 0:
      point = points[loop_num] * a
    else:
      point = 0
      b = loop_num
    if b > 0:
      if loop_num - count + 1 >= b:
        t_max = -10 ** 10
        for j in range(b):
          t = points[j + count] - s
          if t > t_max:
            t_max = t
      else:
        t_max = -10 ** 10
        for j in range(count, loop_num + 1):
          t = points[j] - s
          if t > t_max:
            t_max = t
        for j in range(1, b - loop_num + count):
          t = points[j] + m
          if t > t_max:
            t_max = t
      point += t_max
    #print(point)
    if point > max_point:
      max_point = point
  print(max_point)

### FIXED CODE ###

n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -pow(10, 9)
  #print(max_point)
  for i in range(1, n + 1):
    s = []
    f_pos = positions[i]
    score = scores[f_pos]
    s.append(score)
    while f_pos != i:
      f_pos = positions[f_pos]
      score += scores[f_pos]
      s.append(score)
    loop = len(s)
    if loop >= k:
      point = max(s[:k])
    elif s[-1] <= 0:
      point = max(s)
    else:
      loop_c = k // loop
      r = k % loop
      point1 = s[-1] * loop_c
      if r != 0:
        point1 += max(s[:r])
      point2 = s[-1] * (loop_c - 1)
      point2 += max(0, max(s))
      point = max(point1, point2)
    max_point = max(max_point, point)
  print(max_point)
s_in = S
if s_in[2]==s_in[3] and s_in[4]==s_in[5]:
    print('yes')
else:
    print('no')

### FIXED CODE ###

s_in = input()
if s_in[2]==s_in[3] and s_in[4]==s_in[5]:
    print('Yes')
else:
    print('No')
# -*- coding: utf-8 -*-

"""
計算式は以下のように示される
C_n = (1/n)*(1+C_(n-1)) + ((n-1)/n)*C_(n-1)  =  C_(n-1)+(1/n)
"""
import math
N = int(input())
X = list(map(int, input().split()))

def calc(n):
    if n==1:
        return 1.0
    return calc(n-1)+(1.0/n)

ev=0
for i in range(1,N):
    ev += (X[i]-X[i-1])*calc(i)

print(ev*math.factorial(N-1)%(10**9+7))

### FIXED CODE ###

# -*- coding: utf-8 -*-

mod = 10**9 +7
N = int(input())
X = list(map(int, input().split()))

factorial=[1]
for i in range(1,N):
    factorial.append(factorial[-1] *i %mod)

ans=0
for i in range(1,N):
    ans = (ans*i + (X[-1]-X[i-1])*factorial[i-1]) %mod

print(ans)
a = int(input())
x = list(map(int,input().split()))
t = range(1,a+1)
A = []
B = []
for i in range(1,a+1):
    A.append(30000*i)
    B.append(30000*(a-i+1)+t[x[i-1]])
print(*A)
print(*B)


### FIXED CODE ###

a = int(input())
x = list(map(int,input().split()))
t = range(1,a+1)
A = []
B = []
for i in range(1,a+1):
    A.append(30000*i)
    B.append(30000*(a-i+1))
for i ,d in enumerate(x):
    A[d-1] -= a-i
print(*A)
print(*B)
X, K, D = (list(map(int, input('').split(' '))))
dX = np.arange(-K,K+1,2)
new_X = X + D * dX
print(np.min(np.abs(new_X)))

### FIXED CODE ###

import numpy as np
X, K, D = (list(map(int, input('').split(' '))))
X = np.abs(X)

if np.abs(X)/D <= K:
    new_K = K - int(X/D)
    new_X = X - D*int(X/D)
    if new_K%2==0:
        print(new_X)
    else:
        print(np.abs(new_X-D))
else:
    print(np.abs(X-D*K))
x=input()
print(((x//500)*1000)+((x%500//5)*5))

### FIXED CODE ###

x=int(input())
print(((x//500)*1000)+((x%500//5)*5))
# 1行、1変数を受け取るとき
s = int(input())

print(int(s / 500) * 1000) + (int(s % 10 / 5) * 5)

### FIXED CODE ###

# 1行、1変数を受け取るとき
s = int(input())
print((int(s / 500) * 1000) + (int(s % 500 / 5) * 5))
#include<bits/stdc++.h>
 
using namespace std;
typedef long long int ll;
 
int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0);
 
ll n;
cin>>n;

n=n%1000;
if(n>0)n=1000-n;
cout<<n;


	
}
 

### FIXED CODE ###

k = int(input())
n  =1000
t  =[]

for i in range(1,11):
	if n*i-k>=0:
		t.append(n*i-k)

print(min(t))
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''


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

# コストの小さいものから更新していけばいい
C.sort()

# 2のべき乗は先に計算しておく
beki = []
for i in range(3*N+20):
    beki.append(int(math.pow(2, i)))


ans = 0
for i in range(N):
    ans += (C[i] * beki[2*N-2] * (N-i+1))
    

print(ans % MOD)


### FIXED CODE ###

import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''


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

# コストの小さいものから更新していけばいい
C.sort()

# 2のべき乗は先に計算しておく
beki = [1]
for i in range(1, 3*N+20):
    beki.append((beki[i-1]*2)%MOD)


ans = 0
for i in range(N):
    ans += (C[i] * beki[2*N-2] * (N-i+1))%MOD
    

print(ans % MOD)
#!/usr/bin/env python3

import sys
import math
import itertools

def main():
    n, m = map(int, sys.stdin.readline().split())
    ss, cs = map(list, zip(*(map(int, sys.stdin.readline().split()) for _ in range(m))))

    ans = [None for _ in range(n)]

    for i in range(m):
        if ans[ss[i] - 1] is None:
            ans[ss[i] - 1] = cs[i]
        elif ans[ss[i] - 1] != cs[i]:
            return "-1"

    if n == 1:
        if ans[0] == None:
            return "0"
        else:
            return str(ans[0])

    if ans[0] == 0:
        return "-1"

    for k in range(n):
        if ans[k] is None:
            if k == 0:
                ans[k] = 1
            else:
                ans[k] = 0

    return ''.join(map(str, ans))

if __name__ == '__main__':
    print(main())


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
import itertools

def main():
    n, m = map(int, sys.stdin.readline().split())
    if m == 0:
        ss = []
        cs = []
    else:
        ss, cs = map(list, zip(*(map(int, sys.stdin.readline().split()) for _ in range(m))))

    ans = [None for _ in range(n)]

    for i in range(m):
        if ans[ss[i] - 1] is None:
            ans[ss[i] - 1] = cs[i]
        elif ans[ss[i] - 1] != cs[i]:
            return "-1"

    if n == 1:
        if ans[0] is None:
            return "0"
        else:
            return str(ans[0])

    if ans[0] == 0:
        return "-1"

    for k in range(n):
        if ans[k] is None:
            if k == 0:
                ans[k] = 1
            else:
                ans[k] = 0

    return ''.join(map(str, ans))

if __name__ == '__main__':
    print(main())
def trace(i, j, S, col, num_color):
    next_col = 1 - col
    num_color[col] += 1
    S[i][j] = 2
    if S[i-1][j] == next_col:
        trace(i-1, j, S, next_col, num_color)
    if S[i][j-1] == next_col:
        trace(i, j-1, S, next_col, num_color)
    if S[i+1][j] == next_col:
        trace(i+1, j, S, next_col, num_color)
    if S[i][j+1] == next_col:
        trace(i, j+1, S, next_col, num_color)
    return num_color[0] * num_color[1]

H, W = map(int, input().split())
# 黒0，白1，padding2
S = [[2] * (W+2)]
for _ in range(H):
    S.append([2] + [0 if s == '#' else 1 for s in input()] + [2])
S.append([2] * (W+2))
# print(S)
num_comb = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i][j] == 0:
            num_color = [0, 0]
            num_comb += trace(i, j, S, 0, num_color)
print(num_comb)


### FIXED CODE ###

N = int(input())
H = int(input())
W = int(input())
print((N-H+1) * (N-W+1))
n = int(input())
nums = [int(i) for i in input().split()]
ans = 0

while True:
  if [i for i in nums if i % 2 == 1]
  	break
  nums = [i/2 for i in nums]
  ans += 1 
  
print(ans)


### FIXED CODE ###

n = int(input())
nums = [int(i) for i in input().split()]
ans = 0
while True:
    if [i for i in nums if i % 2 == 1]:
        break
    nums = [i//2 for i in nums]
    ans += 1
print(ans)
#N = str(input())
N,A,B = map(int,input().split())
#X=list(map(int,input().split()))

if A==0:
    print(0)
else:
    b=N//(A+B)
    x=N%(A+B)

if x>A:
    print(b*A+A)
else:
    print(b*A+x)


### FIXED CODE ###

#N = str(input())
N,A,B = map(int,input().split())
#X=list(map(int,input().split()))

if A==0:
    print(0)
    exit()
else:
    b=N//(A+B)
    x=N%(A+B)

    if x>A:
        print(b*A+A)
    else:
        print(b*A+x)