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

n,q=map(int,input().split())
s=list(map(int,input().replace("AC"," 1 0 ").replace("A"," 0 ").replace("T"," 0 ").replace("C"," 0 ").replace("G"," 0 ").replace("  "," ").split()))
for i in range(q):
  l,r=map(int,input().split())
  print(sum(s[l-1:r-1]))

### FIXED CODE ###

n,q=map(int,input().split())
l=[0 for i in range(n)]
for i,v in enumerate(list(input().replace("AC","X!"))):
    l[i]=l[i-1]+(v=="!")
for c in range(q):
    h,m=map(int,input().split())
    print(l[m-1]-l[h-1])
### BUGGY CODE ###

n,k=(int(i) for i in input().split())

w0=[0 for i in range(n+1)]
v0=[0 for i in range(n+1)]
for i in range(1,n+1):
  (w0[i],v0[i]) = (int(i) for i in input().split())
  
w=[0]
v=[0]
for j in range(1,n+1):
    for i in range(len(w)):
        if w[i]+w0[j] <= k:
            w.append(w[i]+w0[j])
            v.append(v[i]+v0[j])  

#print(n,k,w0,v0)
print(max(v))


### FIXED CODE ###

n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

dp=[[0 for i in range(k+1)] for j in range(n+1)]

for i in range(n-1,-1,-1):
  for j in range(k+1):
    if j < e[i][0]:
      dp[i][j]=dp[i+1][j]
    else:
      dp[i][j]=max(dp[i+1][j],dp[i+1][j-e[i][0]]+e[i][1])

print(max(dp[0]))
### BUGGY CODE ###

N, M = map(int, input().split())
base = [[int(l) for l in input().split()] for i in range(M)]
sort_target = sorted(base)
 
  
prefecture_index = sort_target[0][0]
i=0
result = []
for target in sort_target:
  i = i + 1 if prefecture_index == target[0] else 1
  prefecture_index = target[0]
  result.append([base.index(target), "{:0=6}{:0=6}".format(target[0], i)])
 
sorted_result = sorted(result) 
for result in sorted_result:
  print(result[1])

### FIXED CODE ###

N, M = map(int, input().split())
base = []
for i in range(M):
  (a, b) = map(int, input().split())
  base.append((a, b, i))
sorted_target = sorted(base) 

prefecture_index = sorted_target[0][0]

i=0
result = {}

for target in sorted_target:
  if prefecture_index == target[0]:
    i+=1
  else:
    prefecture_index = target[0]
    i = 1
  result[target[2]] = [prefecture_index, i]

for i in range(M):
  print("{:0=6}{:0=6}".format(result[i][0], result[i][1]))
### BUGGY CODE ###

S = input()
X, Y = map(int, input().split())

if S.find("F") < 0:
    if X != 0 or Y != 0:
        print("No")
        exit()

n = len(S)
d = list(map(len, S.split("T")))
xs = d[::2]
ys = d[1::2]

dpx = [[False] * (2 * n + 1) for _ in range(len(xs))]
for i in range(len(xs)):
    if i == 0:
        d = (-1) ** S.find("F")
        dpx[i][d * xs[i] + n] = True
        continue

    for j in range(2 * n + 1):
        if j + xs[i] <= 2 * n:
            dpx[i][j] |= dpx[i - 1][j + xs[i]]
        if 0 <= j - xs[i] <= 2 * n:
            dpx[i][j] |= dpx[i - 1][j - xs[i]]

dpy = [[False] * (2 * n + 1) for _ in range(len(ys) + 1)]
dpy[0][n] = True
for i in range(len(ys)):
    for j in range(2 * n + 1):
        if j + ys[i] <= 2 * n:
            dpy[i + 1][j] |= dpy[i][j + ys[i]]
        if 0 <= j - ys[i] <= 2 * n:
            dpy[i + 1][j] |= dpy[i][j - ys[i]]

ans = dpx[-1][X + n] & dpy[-1][Y + n]
print("Yes" if ans else "No")


### FIXED CODE ###

S = input()
X, Y = map(int, input().split())

if S.find("F") < 0:
    if X != 0 or Y != 0:
        print("No")
    else:
        print("Yes")
    exit()

n = len(S)
d = list(map(len, S.split("T")))
xs = d[::2]
ys = d[1::2]

dpx = [set() for _ in range(len(xs))]
for i in range(len(xs)):
    if i == 0:
        d = (-1) ** S.find("F")
        dpx[i].add(d * xs[i] + n)
        continue
    
    for j in dpx[i - 1]:
        dpx[i].add(j + xs[i])
        dpx[i].add(j - xs[i])

dpy = [set() for _ in range(len(ys) + 1)]
dpy[0].add(n)
for i in range(len(ys)):
    for j in dpy[i]:
        dpy[i + 1].add(j + ys[i])
        dpy[i + 1].add(j - ys[i])

ans = (X + n in dpx[-1]) & (Y + n in dpy[-1])
print("Yes" if ans else "No")
### BUGGY CODE ###

n,k = map(int, input().split())
l = [0] + list(map(int, input().split()))
a = list()
for i in range(n):
  l[i+1] += l[i]
a = [l[j]-l[i] for i in range(n) for j in range(i+1,n+1)]
x = 0
for i in range(40,-1,-1):
  t = 2**i
  if sum(map(lambda y:((y&(t+x)) == t+x),a)) >= k:
    x += t
print(x)

### FIXED CODE ###

n,k = map(int, input().split())
l = [0] + list(map(int, input().split()))
a = list()
for i in range(n):
  l[i+1] += l[i]
a = [l[j]-l[i] for i in range(n) for j in range(i+1,n+1)]
x = 0
for i in range(40,-1,-1):
  t = 2**i 
  if sum(map(lambda y:((y&(t+x)) == t+x),a)) >= k:
    x += t
print(x)
### BUGGY CODE ###

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

if A==B and B==C:
  ans = 0
else:
  for i in range(K):
    A, B, C = B+C, A+C, A+B
    if abs(A-B)>10**18:
      break
  ans = A-B
  
if abs(ans)>10**18:
  print("Unfair")
else:
  print(ans)

### FIXED CODE ###

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

if K%2==1:
  print(-A+B)
else:
  print(A-B)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)


def main():
    n = int(input())
    l_dic = {}
    r_dic = {}
    i = 0
    for a in map(int, input().split()):
        ld = l_dic.setdefault(i + a, [])       
        ld.append(i)
        rd = r_dic.setdefault(i-a, [])
        rd.append(i)
        i += 1
    
    count = 0
    for rk, rv_list in r_dic.items():
        if rk not in l_dic:
            continue
        lv_list = l_dic[rk]
        for rv in rv_list:
            count += len([lv for lv in lv_list if lv < rv])
    
    print(count)



main()



### FIXED CODE ###

def is_ok(mid: int, target: int, ls: []):
    return target <= ls[mid]


def bi_search(target: int, ls: []):
    ng = -1
    ok = len(ls)

    cnt = 0
    while ok - ng > 1:
        mid = ng + int((ok - ng) / 2)
        cnt += 1
        if is_ok(mid, target, ls):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    n = int(input())
    l_dic = {}
    r_dic = {}
    i = 0
    for a in map(int, input().split()):
        ld = l_dic.setdefault(i + a, [])
        ld.append(i)
        rd = r_dic.setdefault(i - a, [])
        rd.append(i)
        i += 1

    count = 0
    for rk, rv_list in r_dic.items():
        if rk not in l_dic:
            continue
        lv_list = l_dic[rk]
        for rv in rv_list:
            ind = bi_search(rv, lv_list)
            if ind == len(lv_list):
                count += ind
            else:
                count += ind + 1
            # for lv in lv_list:
            #     if lv < rv:
            #         count += 1
            #     else:
            #         break

    print(count)


main()
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
dist = set(s)
dic = {}
ans = []

for i in dist:
    dic.update({i: s.count(i)})

max_num = max(dic.values())

for i in dic:
    if dic[i] == max_num:
        ans.append(i)

ans = sorted(ans)
for i in ans:
    print(i)


### FIXED CODE ###

from collections import Counter
n = int(input())
s = sorted([input() for i in range(n)])

counter = Counter(s)
max_num = max(counter.values())
ans_list = [i for i in counter if counter[i] == max_num]
for i in sorted(ans_list):
    print(i)
### BUGGY CODE ###

from itertools import groupby
from math import factorial


def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors


def comb(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


N, M = map(int, input().split())
result = 1

for k, g in groupby(prime_factors(M)):
    result = result * comb(len(list(g)) + N - 1, N - 1)
    result = result % (10 ** 9 + 7)

print(result)


### FIXED CODE ###

import operator as op
from itertools import groupby
from functools import reduce

NN = 10 ** 9 + 7


def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n


def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom


N, M = map(int, input().split())
result = 1

for k, g in groupby(prime_factors(M)):
    result = result * ncr(len(list(g)) + N - 1, N - 1)
    if result > NN:
        result = result % NN

print(result)
### BUGGY CODE ###

n=int(input())
r=0
l=[]
for i in range(n):
  s=input()
  if s not in l:
    r+=1
    l.append(s)
print(r)

### FIXED CODE ###

n=int(input())
r=1
l=[]
for i in range(n):
  l.append(input())
l.sort()
for i in range(n-1):
  if l[i]!=l[i+1]:
    r+=1
  
print(r)
### BUGGY CODE ###

s=input()
t=input()
ma=0
a=[0,0]
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
pred=[[-1 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        dp[i][j]=max(dp[i][j],dp[i-1][j])
        dp[i][j]=max(dp[i][j],dp[i][j-1])
        if s[i-1]==t[j-1]:
            dp[i][j]=max(dp[i][j],1+dp[i-1][j-1])
        if dp[i][j]==1+dp[i-1][j-1]:
            pred[i][j]=[i-1,j-1]
        if dp[i][j]==dp[i][j-1]:
            pred[i][j]=[i,j-1]
        if dp[i][j]==dp[i-1][j]:
            pred[i][j]=[i-1,j]
        if dp[i][j]>ma:
            ma=dp[i][j]
            a=[i,j]
b=a

ans=[b[:]]
while b!=-1:
    #print(b)
    b=pred[b[0]][b[1]]
    if b==-1:
        break
    if 0 in b:
        break
    if b!=-1:
        ans.append(b[:])


ss=""
for  i in ans:
    if s[i[0]-1]==t[i[1]-1]:
        ss+=s[i[0]-1]
ss=ss[-1::-1]
print(ss)
    


### FIXED CODE ###

s=input()
t=input()
ma=0
a=[0,0]
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        if s[i-1]==t[j-1]:
            dp[i][j]=max(dp[i][j],1+dp[i-1][j-1])
i=len(s)
j=len(t)

ss=""
while i and j:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ss+=s[i-1]
        i-=1
        j-=1
ss=ss[-1::-1]
print(ss)
### BUGGY CODE ###

class Solution:

    def solve(self, N: int, P: int, S: str):

        if P == 2 or P == 5:
            answer = 0
            for idx, s in enumerate(S):
                if int(s) % P == 0:
                    answer += idx + 1

        else:
            answer = 0
            U = [0] * P  # int(S[i,N] mod P
            U[0] += 1
            for i in range(N):
                U[int(S[i:N]) % P] += 1

            for u in U:
                answer += u * (u-1) // 2

        return answer


if __name__ == '__main__':

    # standard input
    N, P = map(int, input().split())
    S = input()

    # solve
    solution = Solution()
    answer = solution.solve(N, P, S)
    print(answer)


### FIXED CODE ###

class Solution:

    def solve(self, N: int, P: int, S: str):

        if P == 2 or P == 5:
            answer = 0
            for idx, s in enumerate(S):
                if int(s) % P == 0:
                    answer += idx + 1

        else:
            answer = 0
            U = [0] * P  # int(S[i,N] mod P
            U[0] += 1

            num = 0
            base10_mod_p = 1
            for i in range(N):
                num = (num + int(S[N-i-1]) * base10_mod_p) % P
                base10_mod_p = (base10_mod_p * 10) % P

                U[num] += 1

            for u in U:
                answer += u * (u-1) // 2

        return answer


if __name__ == '__main__':

    # standard input
    N, P = map(int, input().split())
    S = input()

    # solve
    solution = Solution()
    answer = solution.solve(N, P, S)
    print(answer)
### BUGGY CODE ###

S = input()
Slist = [S[i] for i in range(len(S))]
Q = int(input())
Query = [list(input().split()) for i in range(Q)]
for idx, value in enumerate(Query):
    if int(value[0]) == 1:
        Slist= Slist[::-1]
    else:
        if int(value[1]) == 1:
            Slist = [value[2]] + Slist
        else:
            Slist.append(value[2])
print("".join(Slist))

### FIXED CODE ###

S = input()
Slist = [S[i] for i in range(len(S))]
Q = int(input())
Query = [list(input().split()) for i in range(Q)]
Qlen = len(Query)
reverse = False
back = []
head = []

for idx, value in enumerate(Query):
    if value[0] == "1":
        reverse ^= True
        head, back = back, head
    else:
        if value[1] == "1":
            head += [value[2]]
        else:
            back += [value[2]]

if reverse == False:
    head.reverse()
    print("".join(head + Slist + back))
else:
    head.reverse()
    print("".join(head + Slist[::-1] + back))
### BUGGY CODE ###

import sys
cnt = 1
while 1:
    for x in sys.stdin.readline().strip():
        if x == 0:break
    print('Case{}:{}'.format(cnt,x))
    cnt += 1

### FIXED CODE ###

import sys
cnt = 1
while 1:
    x = sys.stdin.readline().strip()
    if x == '0':
        break;
    print('Case %d: %s'%(cnt,x))
    cnt += 1
### BUGGY CODE ###

n=int(input())
d_s=input().split()
d=[int(x) for x in d_s]
judge=0
count=0
for i in range(1,100000):
  for x in d:
    if x==i:
      count+=1
  if count==n/2:
    judge+=1
  elif count>n/2:
    break
print(judge)

### FIXED CODE ###

n=int(input())
d_s=input().split()
d_i=[int(x) for x in d_s]
d=sorted(d_i)
k=d[int(n/2)]
t=d[int(n/2)-1]
print(k-t)
### BUGGY CODE ###

ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########

def resolve():
    n = ii()
    a = mi()
    res = 1
    for i in a:
        res = res * i
    print(res if res <= 10**18 else -1)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########

def resolve():
    n = ii()
    a = mi()
    if 0 in a:
        print(0)
        return
    res = 1
    for i in a:
        res = res * i
        if(res > 10**18):
            print(-1)
            return
    print(res)

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

import collections

N = int(input())

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

Q = int(input())

B = []
C = []
for i in range(Q):
    b, c = map(int,input().split())
    B.append(b)
    C.append(c)

# print(N,A,Q,B,C)


a = []

a = dict(collections.Counter(A))

# print(a)


# d1 = {'k1': 1, 'k2': 2}
# d2 = {'k1': 100, 'k3': 3, 'k4': 4}

# d1.update(d2)
# print(d1)
# # {'k1': 100, 'k2': 2, 'k3': 3, 'k4': 4}

# これを用いれば良い。

for i in range(Q):
    # 変更後
    after = {B[i]: 0, C[i]: a.setdefault(B[i], 0) + a.setdefault(C[i], 0)}
    # print(a, after)
    a.update(after)

    s = 0
    for k in a:
        s += k * a[k]
    print(s)

# print(a)



### FIXED CODE ###

import collections

N = int(input())

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

Q = int(input())

B = []
C = []
for i in range(Q):
    b, c = map(int,input().split())
    B.append(b)
    C.append(c)

# print(N,A,Q,B,C)


a = []

a = dict(collections.Counter(A))

s = 0
for k in a:
    s += k * a[k]
# print(s)

# sに対する増減だけ管理する

for i in range(Q):
    # 変更後
    after = {B[i]: 0, C[i]: a.setdefault(B[i], 0) + a.setdefault(C[i], 0)}
    # print(a, after)

    s = s + (C[i] - B[i] ) * a[B[i]]

    print(s)

    a.update(after)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from fractions import gcd


def lcd(x, y):
    g = gcd(x, y)
    return x * y // g


def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    l = 1
    for e in a:
        l = lcd(l, e)

    ans = 0
    for e in a:
        ans += l // e
        ans %= mod

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from fractions import gcd


def lcm(a, b):
    return a * b // gcd(a, b)


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

l = 1
for e in a:
    l = lcm(l, e)

l %= mod

ans = 0
for e in a:
    ans += l * pow(e, mod - 2, mod)
    ans %= mod

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

import sys
import queue

h, w = list(map(int, input().split()))
l = [input() for _ in range(h)]
checked = [[False for _ in range(w)] for __ in range(h)]

q = queue.Queue()
q.put((0, 0, 1))
checked[0][0] = True
while not q.empty():
    x, y, count = q.get()
    checked[y][x] = True
    if x == w-1 and y == h-1:
        ans = 0
        for i in range(h):
            for j in range(w):
                if l[i][j] == ".":
                    ans += 1
        print(ans-count)
        sys.exit(0)
    if x > 0 and l[y][x-1] == "." and not checked[y][x-1]:
        q.put((x-1, y, count+1))
    if y > 0 and l[y-1][x] == "." and not checked[y-1][x]:
        q.put((x, y-1, count+1))
    if x < w-1 and l[y][x+1] == "." and not checked[y][x+1]:
        q.put((x+1, y, count+1))
    if y < h-1 and l[y+1][x] == "." and not checked[y+1][x]:
        q.put((x, y+1, count+1))
print(-1)

### FIXED CODE ###

import sys
import queue

h, w = list(map(int, input().split()))
l = [input() for _ in range(h)]
checked = [[False for _ in range(w)] for __ in range(h)]

q = queue.Queue()
q.put((0, 0, 1))
while not q.empty():
    x, y, count = q.get()
    if checked[y][x]:
        continue
    checked[y][x] = True
    if x == w-1 and y == h-1:
        ans = 0
        for i in range(h):
            for j in range(w):
                if l[i][j] == ".":
                    ans += 1
        print(ans-count)
        sys.exit(0)
    if x > 0 and l[y][x-1] == "." and not checked[y][x-1]:
        q.put((x-1, y, count+1))
    if y > 0 and l[y-1][x] == "." and not checked[y-1][x]:
        q.put((x, y-1, count+1))
    if x < w-1 and l[y][x+1] == "." and not checked[y][x+1]:
        q.put((x+1, y, count+1))
    if y < h-1 and l[y+1][x] == "." and not checked[y+1][x]:
        q.put((x, y+1, count+1))
print(-1)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  a,b,n=LI()

  # right=n
  # ans=math.floor(a*right/b)-a*math.floor(right/b)
  # left=0
  # while left<=right:
  #   half=(left+right)//2
  #   _ans=math.floor(a*half/b)-a*math.floor(half/b)
  #   if _ans==ans:
  #     return ans
  #   elif _ans>ans:
  #     right=half-1
  #     ans=_ans
  #   else:
  #     left=half+1

  ans=int(a*1/b)-a*int(1/b)
  x=int(math.sqrt(n))
  for i in range(max(0,n-x-100000000),n+1):
    ans=max(ans,int(a*i//b)-a*int(i//b))
  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  # floor(x/b)がギリギリ割り切れない辺りが一番大きくなりそう
  # -> 実験してみるとmath.floor(a*x/b)-a*math.floor(x/b)はループしてそう
  # -> 答えはfloor(x/b)がギリギリ割り切れないときの値に決め打つぜ！
  a,b,n=LI()
  x=min(n,b-1)
  return math.floor(a*x/b)-a*math.floor(x/b)

# main()
print(main())
### BUGGY CODE ###

H, W, M = map(int, input().split())
S = [[0 for _ in range(W)] for i in range(H)]
bombs_h = [0] * H
bombs_w = [0] * W
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    S[h][w] = 1
    bombs_h[h] += 1
    bombs_w[w] += 1

max_h = max(bombs_h)
max_w = max(bombs_w)
hs = [i for i, x in enumerate(bombs_h) if x == max_h]
ws = [i for i, x in enumerate(bombs_w) if x == max_w]
p = 1
for i in hs:
    for j in ws:
        if S[i][j] == 0:
            p = 0
            break
ans = max_w + max_h - p
print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())
bombs_h = [0] * H
bombs_w = [0] * W
B = []
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    B.append((h, w))
    bombs_h[h] += 1
    bombs_w[w] += 1

max_h = max(bombs_h)
max_w = max(bombs_w)
hs = [i for i, x in enumerate(bombs_h) if x == max_h]
ws = [i for i, x in enumerate(bombs_w) if x == max_w]
k = len(hs)*len(ws)
cnt = 0
for h, w in B:
    if bombs_h[h] == max_h and bombs_w[w] == max_w:
        cnt += 1
ans = max_w + max_h - (cnt == k)
print(ans)
### BUGGY CODE ###

#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys
from collections import defaultdict

  
def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def _main():
    h, w, a, b = get_ints()

    list2 = defaultdict(int)
    for j in range(0, w):
        list2[0, j] = 1
    for i in range(1, h-a):
        list2[i, 0] = 1
    for i in range(1, h-a):
        for j in range(1, w):
            list2[i, j] = list2[i - 1, j] + list2[i, j - 1]
    for i in range(h-a, h):
        list2[i, b] = list2[i-1, b]
    for i in range(h-a, h):
        for j in range(b+1, w):
            list2[i, j] = list2[i - 1, j] + list2[i, j - 1]

    print(list2[h-1, w-1] % (10**9 + 7))


if __name__ == "__main__":
    _main()


### FIXED CODE ###

#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def mul(x, y, mod):
    x %= mod
    y %= mod
    return x * y % mod


def div(x, y, mod):
    x %= mod
    y %= mod
    return x * mod_pow(y, mod - 2, mod) % mod


def mod_pow(a, p, mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        root = mod_pow(a, p / 2, mod)
        return root * root % mod
    else:
        return a * mod_pow(a, p - 1, mod) % mod


def pre_factorial_divs(n, mod, factorials):
    factorial_divs = [0] * (n + 1)

    factorial_divs[n] = div(1, factorials, mod)
    for i in reversed(range(n)):
        factorial_divs[i] = mul(factorial_divs[i+1], i+1, mod)
    return factorial_divs


def pre_factorials(n, mod):
    factorials = [0] * (n + 1)
    factorials[0] = 1
    for i in range(n):
        factorials[i + 1] = (i + 1) * factorials[i] % mod
    return factorials


def fast_fast_fermat_comb(a, b, mod, factorials, factorial_divs):
    if len(factorials) == 0:
        raise
    af = factorials[a]
    bf = factorial_divs[b]
    abf = factorial_divs[a - b]
    return mul(mul(af, bf, mod), abf, mod)


def main():
    h, w, a, b = get_ints()

    ans = 0
    mod = 10 ** 9 + 7

    factorials = pre_factorials(h+w-2, mod)
    factorial_divs = pre_factorial_divs(h+w-2, mod, factorials[h+w-2])

    for i in range(h-a):
        x = fast_fast_fermat_comb(b-1+i, b-1, mod, factorials, factorial_divs)
        y = fast_fast_fermat_comb(h+w-3-(b-1+i), w-b-1, mod, factorials, factorial_divs)
        ans += x * y % mod
        ans %= mod

    print(ans)


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

N = int(input())
count = 1+N
for i in range(1,N):
  if N % i == 0 and i + N/i < count:
    count = i+ N/i
count = int(count)
print(count-2)

### FIXED CODE ###

N = int(input())
count = 1+N
for i in range(1,int(N**0.5)+1):
  if N % i == 0 and i + N/i < count:
    count = i+ N/i
count = int(count)
print(count-2)
### BUGGY CODE ###

S = list(input())
S.reverse()

cnt = [0] * 2019
total = 0
x = 1
ans = 0

for a in S:
    cnt[total] += 1
    total += int(a) * x
    total %= 2019
    ans += cnt[total]
    x = x*10

print(ans)

### FIXED CODE ###

s=input()
n=len(s)
mod=2019
d=0
p=1
ml=[0]*mod
for i in range(1,n+1):
  k=int(s[-i])
  d+=p*k
  d%=mod
  ml[d]+=1
  p*=10
  p%=mod
ans=0
for i in ml:
  ans+=i*(i-1)//2
print(ans+ml[0])