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

L = input()
n = len(L)
csum_1 = [0] * n
csum_0 = [0] * n
now1 = 0
now0 = 0
for i in range(n):
    if L[i] == '1':
        now1 += 1
    else:
        now0 += 1
    csum_1[i] = now1
    csum_0[i] = now0

mod = 10**9+7
ans = 0
# iは、「最初にL[i]=1かつai=0かつbi=0となるindex」
for i in range(n):
    if L[i] == '1':
        p = 1
        # 自分より左側の0の度に2パターン増加
        if i >= 1:
            p *= 2**csum_1[i-1]
        #print(p)
        p %= mod
        # 自分より右側はどの桁も3パターン増加
        p *= 3**(n-i-1)
        #print(p)
        p %= mod
        ans += p
        ans %= mod
# L=a+bの場合
p = 2**(csum_1[-1])
p %= mod
#print(p)
ans = (ans+p)%mod
print(ans)

### FIXED CODE ###

L = input()
n = len(L)
csum_1 = [0] * n
csum_0 = [0] * n
now1 = 0
now0 = 0
for i in range(n):
    if L[i] == '1':
        now1 += 1
    else:
        now0 += 1
    csum_1[i] = now1
    csum_0[i] = now0

mod = 10**9+7
ans = 0
# iは、「最初にL[i]=1かつai=0かつbi=0となるindex」
for i in range(n):
    if L[i] == '1':
        p = 1
        # 自分より左側の0の度に2パターン増加
        if i >= 1:
            p *= pow(2,csum_1[i-1],mod)
        #print(p)
        # 自分より右側はどの桁も3パターン増加
        p *= pow(3,n-i-1,mod)
        #print(p)
        ans += p
        ans %= mod
# L=a+bの場合
p = pow(2,csum_1[-1],mod)
#print(p)
ans = (ans+p)%mod
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
path=[[0 if i<=j else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

seen=[0]*N
dist=[float("inf")]*N
dist[0]=0
v=-1
while v!=N-1:
  v=-1
  for i in range(N):
    if seen[i]==0 and v==-1:
      v=i
    if seen[i]==0 and dist[i]<dist[v]:
      v=i
  seen[v]=1
  for i in range(N):
    dist[i]=min(dist[v]+path[v][i],dist[i])
    
if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
path=[[] for _ in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1].append([r,c])
for i in range(1,N):
  path[i].append([i,0])

dist=[float("inf")]*N
dist[0]=0
q=[[dist[i],i] for i in range(N)]
heapq.heapify(q)

while q:
  d,ind=heapq.heappop(q)
  if d<=dist[ind]:
    for i in range(len(path[ind])):
      r,c=path[ind][i]
      if dist[r-1]>d+c:
        dist[r-1]=d+c
        heapq.heappush(q,[dist[r-1],r-1])

if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])
### BUGGY CODE ###

N, M= (int(i) for i in input().split())  
A = [int(i) for i in input().split()]

BClist = []
for i in range(M):
	B,C = [int(i) for i in input().split()]
	for g in range(B):
		BClist.append(C)
A.sort()
BClist.sort()

for i in range(len(BClist)):
	if A[i]<BClist[-1]:
		A[i]=BClist[-1]
		BClist.pop(-1)
	else:
		break
print(sum(A))

### FIXED CODE ###

import heapq

n,m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]
bc.sort(key=lambda x: x[1],reverse=True)

heapq.heapify(a)

for i in range(m):
    b,c=bc[i]
    for g in range(b):
        _min = heapq.heappop(a)
        if _min<c:
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,_min)
            break
print(sum(a))
### BUGGY CODE ###

N, K, C = map(int, input().split())
S = list(input())
#left_greedy
count = 0
switch = 0
left_greedy = [0]*len(S)
right_greedy=[0]*len(S)
clist = [0]*len(S)
for l in range(len(S)):
    i = S[l]
    if switch ==1:
        if i == 'o':
            if count >= C:
                left_greedy[l]=1
                clist[l] = count
                count = 0
            else:
                count+=1
                clist[l] = count
        else:
            count+=1
            clist[l] = count
    else:
        if i == 'o':
            left_greedy[l]=1
            switch+=1
#left_greedy
switch = 0
for r in range(len(S)-1, 0, -1):
    i = S[r]
    if switch ==1:
        if i == 'o':
            if count >= C:
                right_greedy[r]=1
                clist[r] = count
                count = 0
            else:
                count+=1
                clist[l] = count
        else:
            count+=1
            clist[l] = count
    else:
        if i == 'o':
            right_greedy[r]=1
            switch+=1
for i in range(len(S)):
    if S[i] ==  'o':
        l = left_greedy[0:i].count(1)
        r = right_greedy[i+1:len(S)].count(1)
        x = r+l
        if 1 in left_greedy[0:i][::-1]:
            if 1 in right_greedy[i+1:len(S)-1]:
                if left_greedy[0:i][::-1].index(1)+right_greedy[i+1:len(S)-1][::-1].index(1)+1 < C:
                    x+=-1
        if x < K:
            print(i+1)

### FIXED CODE ###

n,k,c = list(map(int,input().split()));s=[True if i=="o" else False for i in input()]
front=[0]*n;back=[0]*n;count=0
 
day = 0
while day < n:
    if s[day]:
        count += 1
        front[day]= 1
        day += c+1
    else:
        day += 1
    
s = s[::-1]
day = 0
while day < n:
    if s[day]:
        back[day]= 1
        day += c+1
    else:
        day += 1
back = back[::-1]
    
if count ==k:
    for i in range(n):
        if front[i] ==1 and back[i] == 1:
            print(i+1)
### BUGGY CODE ###

def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from itertools import permutations
def solve(N):
    return sum(len(find_factors(i)) for i in range(1,N))

def find_factors(num):
    A=[]
    for i in range(1,num+1):
        if num%i==0:
            A.append(i)
    return A
N=readInt()
print(solve(N))

### FIXED CODE ###

def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from itertools import permutations
def solve(N):
    count=0
    for i in range(1,N):
        count+=(N-1)//i
    return count

N=readInt()
print(solve(N))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

ans = []
for i in range(n):
    if a[i] in ans:
        ans.remove(a[i])
    else:
        ans.append(a[i])

print(len(ans))

### FIXED CODE ###

import collections
n = int(input())
a = [int(input()) for i in range(n)]

aa = collections.Counter(a)
ans = 0
for i in aa:
    if aa[i] % 2 == 1:
        ans += 1
    
print(ans)
### BUGGY CODE ###

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

S1 = list(S[:N])
# 左右同じものを目指す形にしたいので、片方はリバースしておく
S2 = list(S[N:])[::-1]

d1 = Counter()
d2 = Counter()
# 半分に分けた両方を組み合わせ全列挙
for i in range(1<<N):
    s1_1, s1_2 = [], []
    s2_1, s2_2 = [], []
    for j in range(N):
        if i>>j & 1:
            s1_1 += [S1[j]]
            s2_1 += [S2[j]]
        else:
            s1_2 += [S1[j]]
            s2_2 += [S2[j]]
    # 文字列ペアをキーとして、その通り数を数えておく
    d1[(''.join(s1_1), ''.join(s1_2))] += 1
    d2[(''.join(s2_1), ''.join(s2_2))] += 1

ans = 0
for k, v in d1.items():
    # 左文字列ペア = 右文字列ペア になるような通り数を数え上げる
    ans += v * d2[k]
print(ans)


### FIXED CODE ###

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

S1 = list(S[:N])
# 左右同じものを目指す形にしたいので、片方はリバースしておく
S2 = list(S[N:])[::-1]

d1 = Counter()
d2 = Counter()
# 半分に分けた両方を組み合わせ全列挙
for i in range(1<<N):
    s1_1, s1_2 = [], []
    s2_1, s2_2 = [], []
    for j in range(N):
        if i>>j & 1:
            s1_1 += [S1[j]]
            s2_1 += [S2[j]]
        else:
            s1_2 += [S1[j]]
            s2_2 += [S2[j]]
    # 文字列ペアをキーとして、その通り数を数えておく
    d1[(''.join(s1_1), ''.join(s1_2))] += 1
    d2[(''.join(s2_1), ''.join(s2_2))] += 1

ans = 0
for k, v in d1.items():
    # 左文字列ペア = 右文字列ペア になるような通り数を数え上げる
    ans += v * d2[k]
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
s = list(input())
# print(n, k, s)

a = []
cnt = 0
for i in range(n-1):
    cnt += 1
    if s[i] != s[i+1]:
        a.append(cnt)
        cnt = 0 # reset
a.append(cnt+1)
# print(a) # 連続する0,1の数の配列を作った
### 前処理 両端が1の数を表す数列を作ることが出来た
if s[0] == "0": # 左端
    a.insert(0, 0)
if s[-1] == "0": # 右端
    a.append(0)
# print(a)
# print((len(a)-2*k+1)//2)
if (len(a)-2*k+1)/2 < 1:
    k = int((len(a)-1)/2)
# print(k)
ans = 0
for i in range((len(a)-2*k+1)//2):
    b = 0
    for j in range(2*k+1):
        b += a[2*i+j]
    # print(i, b)
    ans = max(ans, b) # 最大値を更新していく
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
s = list(input())

# 累積和
a = [0]
if s[0] == "0":
	a.append(0)
for i in range(n):
	if i == n-1 or s[i+1] != s[i]:
		a.append(i+1) # 累積和

# print(s[-1])
if s[-1] == "0":
	a.append(a[-1])

if len(a) <= 2*k+1: # 2*k+1
	print(n)
else:
	ans = 0
	for j in range(0, len(a) - 2*k - 1, 2): # len(a)は奇数
		ans = max(ans, a[j+2*k+1] - a[j])
	print(ans)
### BUGGY CODE ###

n=int(input())
s=input()

def ZA(n,s):
    Z=[0 for i in range(n)]
    Z[0]=n
    i=1
    j=0
    cand=0
    while i<n:
        while i+j<n and s[j]==s[i+j]:
            j+=1
        Z[i]=j
        cand=max(cand,min(Z[i],i))
        if j==0:
            i+=1
            continue
        k=1
        while k<j and k+Z[k]<j:
            Z[i+k]=Z[k]
            cand=max(cand,min(Z[i],i))
            k+=1
        i+=k
        j-=k
    #print(Z)
    return cand


ans=0
for i in range(n):
    ans=max(ans,ZA(n-i,s[i:]))
print(ans)

### FIXED CODE ###

n=int(input())
s=input()

def ZA(n,s):
    Z=[0 for i in range(n)]
    Z[0]=n
    i=1
    j=0
    cand=0
    while i<n:
        while i+j<n and s[j]==s[i+j]:
            j+=1
        Z[i]=j
        cand=max(cand,min(Z[i],i))
        if j==0:
            i+=1
            continue
        k=1
        while k<j and k+Z[k]<j:
            Z[i+k]=Z[k]
            cand=max(cand,min(Z[i],i))
            k+=1
        i+=k
        j-=k
    #print(Z)
    return cand


ans=0
for i in range(n):
    ans=max(ans,ZA(n-i,s[i:]))
print(ans)
### BUGGY CODE ###

n=int(input())
p=list(map(int, input().split()))
ans=1
if p[0]==min(p):
    print(ans)
else:
    l=[p[0]]
    for i in range(1,n):
        l.append(p[i])
        if p[i]==min(l):
            ans+=1
    print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(int, input().split()))
ans=1
l=[p[0]]
buf=p[0]
for i in range(1,n):
    l.append(p[i])
    if p[i]<=buf:
        ans+=1
        buf=p[i]
print(ans)
### BUGGY CODE ###

def solve(s, k):
    n = len(s)
    pdp = [[0] * (k + 1) for _ in range(n + 1)]
    for l in range(n - 1, -1, -1):
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        for r in range(l, n):
            dpr, dpr1 = dp[r], pdp[r - 1]
            inc = 1 if l == r else 2
            is_same = s[l] == s[r]
            for p in range(k + 1):
                if is_same:
                    dpr[p] = dpr1[p] + inc
                else:
                    if p:
                        dpr[p] = max(pdp[r][p], dp[r - 1][p], dpr1[p - 1] + inc)
                    else:
                        dpr[p] = max(pdp[r][p], dp[r - 1][p])
        pdp = dp

    return pdp[-2][k]


print(solve(input(), int(input())))


### FIXED CODE ###

def solve(s, k):
    n = len(s)
    pdp = [[0] * (k + 1) for _ in range(n + 1)]
    for l in range(n - 1, -1, -1):
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        for r in range(l, n):
            dpr, dpr1 = dp[r], pdp[r - 1]
            inc = 1 if l == r else 2
            is_same = s[l] == s[r]
            for p in range(k + 1):
                if is_same:
                    dpr[p] = dpr1[p] + inc
                else:
                    if p:
                        dpr[p] = max(pdp[r][p], dp[r - 1][p], dpr1[p - 1] + inc)
                    else:
                        dpr[p] = max(pdp[r][p], dp[r - 1][p])
        pdp = dp

    return pdp[-2][k]


print(solve(input(), int(input())))
### BUGGY CODE ###

import heapq as hq

N, M = map(int, input().split())
A = []

for i in range(N):
    a, b = map(int, input().split())
    A.append([b * (-1), a * (-1)])


# print(A)
ans = 0
Q = []
hq.heapify(Q)

for i in range(1, M + 1):
    for j in (A):
        if j[1] * (-1) <= i:
            hq.heappush(Q, j)
            A.remove([j[0], j[1]])
            # print(Q)
    if Q:
        ans += hq.heappop(Q)[0] * (-1)


print(ans)


### FIXED CODE ###

import heapq as hq

N, M = map(int, input().split())
A = []

for i in range(N):
    a, b = map(int, input().split())
    A.append([a, b * (-1)])

A.sort()
# print(A)

ans = 0
j = 0
Q = []
hq.heapify(Q)

for i in range(1, M + 1):
    while j < len(A):
        if A[j][0] <= i:
            hq.heappush(Q, A[j][1])
            # print(Q)
        else:
            break
        j += 1
    if Q:
        ans += hq.heappop(Q) * (-1)


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

N=int(input())
n_list= list(map(int,input().split()))
ans=1
tho=10**18
for i in range (N):
  ans*=n_list[i]
  
if ans > tho :
  print ('-1')
elif ans <= tho :
  print(ans)

### FIXED CODE ###

N = int(input())
n_list = list(map(int,input().split()))
if 0 in n_list :
  print('0')
else:  
  ans = 1
  tho = 10**18
  for i in range (N):
    ans *= n_list[i]
    if ans > tho :
      print('-1')
      break
  if ans <= tho :
    print(ans)
### BUGGY CODE ###

def resolve():
    import sys
    import numpy as np

    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for _ in [0] * N]
    
    dp = np.zeros((N, W + 1), np.int64)

    for i in range(N):
        w, v = lst[i][0], lst[i][1]
        for sum_w in range(W + 1):
            if sum_w >= w:
                dp[i][sum_w] = max(dp[i][sum_w],
                                   dp[i - 1][sum_w - w] + v)
            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w])
    print(max(dp[-1]))


resolve()


### FIXED CODE ###

def resolve():
    import sys
    
    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for _ in [0] * N]
    
    dp = [[0] * (W + 1) for _ in [0] * N]

    for i in range(N):
        w, v = lst[i][0], lst[i][1]
        for sum_w in range(W + 1):
            if sum_w >= w:
                dp[i][sum_w] = max(dp[i][sum_w],
                                   dp[i - 1][sum_w - w] + v)
            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w])
    print(max(dp[-1]))


resolve()
### BUGGY CODE ###

INF = 1000000000

def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  V = [s]
  while V:
    v = V.pop(0)
    for e in E[v]:
      if D[v] + e[1] < D[e[0]]:
        D[e[0]] = D[v] + e[1]
        V.append(e[0])
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])
  
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      a = min(lst[1],lst[2])
      b = max(lst[1],lst[2])
      if lst[0] == 0:
        solve(a - 1, b - 1, E, n)
      elif lst[0] == 1:
        E[a - 1].append([b - 1, lst[3]])
        E[b - 1].append([a - 1, lst[3]])
  except EOFError:
    break


### FIXED CODE ###

from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()


    def check(l):
        if l == 0:
            return True
        for i in range(n-l*2+1):
            for j in range(i+l, n-l+1):
                cnt = 0
                for k in range(l):
                    if s[i+k] == s[j+k]:
                        cnt += 1
                    else:
                        break

                if cnt == l:
                    # print(l, i, j, cnt,)
                    return True

        return False


    lb = 0
    ub = n // 2 + 1
    # for i in range(ub+1):
    #     print(i, check(i))

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check(mid):
            lb = mid
        else:
            ub = mid

    print(lb)

main()


### FIXED CODE ###

n = int(input())
s = input()

n += 1
s += "#"

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0

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

class Union:
  def __init__(self, num):
    self.T = [-1 for i in range(num)]

  def root(self, x):
    if self.T[x] < 0: return x
    return self.root(self.T[x])

  def size(self, x):
    return -self.T[self.root(x)]

  def merge(self, x, y):
    a = self.root(x)
    b = self.root(y)
    if a == b: return False
    if self.size(a) < self.size(b): a, b = b, a
    self.T[a] += self.T[b]
    self.T[b] = a
    return True

  def same(self, x, y):
    return self.root(x) == self.root(y)


N, M, K = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

uni = Union(N)
f = [0] * N
for a, b in AB:
  a -= 1
  b -= 1
  uni.merge(a, b)
  f[a] += 1
  f[b] += 1

L = [[] for _ in range(N)]
for c, d in CD:
  c -= 1
  d -= 1
  L[c].append(d)
  L[d].append(c)

ans = [0] * N

for i in range(N):
  k = uni.size(i)
  k -= f[i] + 1
  for j in L[i]:
    if uni.same(i, j):
      k -= 1
  ans[i] = k

ans = map(str, ans)
print(" ".join(ans))

### FIXED CODE ###

class Union:
  def __init__(self, num):
    self.T = [-1 for i in range(num)]

  def root(self, x):
    if self.T[x] < 0: return x
    return self.root(self.T[x])

  def size(self, x):
    return -self.T[self.root(x)]

  def merge(self, x, y):
    a = self.root(x)
    b = self.root(y)
    if a == b: return False
    if self.size(a) < self.size(b): a, b = b, a
    self.T[a] += self.T[b]
    self.T[b] = a
    return True

  def same(self, x, y):
    return self.root(x) == self.root(y)

import sys
input = sys.stdin.readline
N, M, K = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

uni = Union(N)
ans = [-1] * N
for a, b in AB:
  a -= 1
  b -= 1
  uni.merge(a, b)
  ans[a] -= 1
  ans[b] -= 1

L = [[] for _ in range(N)]
for c, d in CD:
  c -= 1
  d -= 1
  L[c].append(d)
  L[d].append(c)

for i in range(N):
  ans[i] += uni.size(i)
  for j in L[i]:
    if uni.same(i, j):
      ans[i] -= 1

ans = map(str, ans)
print(" ".join(ans))
### BUGGY CODE ###

# D - いろはちゃんとマス目
def combmod(n,k,mod):
    a = 1
    b = 1
    for i in range(k):
        a = a * (n-i) % mod
        b = b * (i+1) % mod
    return a * pow(b, mod-2, mod) % mod

h,w,a,b=map(int,input().split())

mod=10**9+7
ans=0
for i in range(b,w):
    ans+=combmod(i+h-1-a,i,mod)*combmod(w-1-i+a-1,a-1,mod)
    ans%=mod
print(ans)


### FIXED CODE ###

# D - いろはちゃんとマス目
def cmb1(n,r,mod):
    if (r<0 or r>n):
        return 0
    r = min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod

h,w,a,b=map(int,input().split())

# 前処理
mod=10**9+7 #出力の制限
n=10**6
g1=[1,1] # 元テーブル
g2=[1,1] # 逆元テーブル
inverse=[0,1] #逆元テーブル計算用テーブル

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

ans = 0
for i in range(b, w):
    ans+=cmb1(i+h-1-a,i,mod)*cmb1(w-1-i+a-1,a-1,mod)
    ans%=mod
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = set(a)
ans = 0
l = []
for i in s:
  if i in a:
    ans += 1
    f = a.index(i)
    a = a[f:]
    l.append(i)
  else:
    break
ll = list(range(1, ans + 1))
if l == ll:
  ans = n - ans
else:
  ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 1
for i in a:
    if i == x:
        x += 1
    else:
        pass
if x == 1:
    print(-1)
else:
    print(n - x + 1)