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

# -*- coding: utf-8 -*-
import queue

n, x, y = map(int, input().split())
x -= 1
y -= 1
INF = 10010101010101
ans = [0 for _ in range(n)]
def put(v, d):
    if dist[v] != INF:
        return
    dist[v] = d
    q.put(v)
for sv in range(n):
    q = queue.Queue()
    dist = [INF for _ in range(n)]
    put(sv, 0)
    while not q.empty():
        v = q.get()
        d = dist[v]
        if v-1 >= 0:
            put(v-1, d+1)
        if v+1 < n:
            put(v+1, d+1)
        if v == x:
            put(y, d+1)
        if v == y:
            put(x, d+1)
    for i in range(n):
        ans[dist[i]] += 1
for i in range(n):
    ans[i] = int(ans[i] / 2)

print(*ans[1:], sep='\n')


### FIXED CODE ###

# -*- coding: utf-8 -*-
n, x, y = map(int, input().split())
x -= 1
y -= 1
ans = [0]*n
for i in range(n):
    for j in range(i + 1, n):
        dist1 = j - i
        dist2 = abs(x - i) + abs(y - j) + 1
        ans[min(dist1, dist2)] += 1
print(*ans[1:], sep='\n')
### BUGGY CODE ###

import collections
N, K = map(int, raw_input().split())
P_list = list()
for i in range(N):
    P_list.append(raw_input()[0])
    C_list = collections.Counter(P_list).values()

# clean
C_list = [c for c in C_list if c > 0]
C_list.sort(reverse=True)

res = 0
while True:
    if len(C_list) >= K:
        d = C_list[K-1]
        for i in range(K):
            C_list[i] -= d
        res += d
        C_list = [c for c in C_list if c > 0]
        C_list.sort(reverse=True)
    else:
        break
print res

### FIXED CODE ###

import numpy as np
C_vec = np.zeros(26)
N, K = map(int, raw_input().split())

for i in range(N):
    C_vec[ord((raw_input()[0])) - ord('A')] += 1


while True:
    m = int(C_vec.sum() / K)
    C_vec = np.minimum(C_vec, m)
    m_next = int(C_vec.sum() / K)
    if m_next == m:
        break
    else:
        m = m_next

print m
### BUGGY CODE ###

import sys

count = 0

number = int(input())

for line in sys.stdin:
    n = int(line)
    if n == 2:
        count += 1
        continue

    if n % 2 == 0:
        continue

    jdg = True
    for i in range(3, int(n/2) + 1, 2):
        if n % i == 0:
            jdg = False
            break
    if jdg:
        count += 1

print(count)



### FIXED CODE ###

import sys

count = 0

number = int(input())

for line in sys.stdin:
    n = int(line)
    if n == 2:
        count += 1
        continue

    if n % 2 == 0:
        continue

    jdg = True
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            jdg = False
            break
    if jdg:
        count += 1

print(count)
### BUGGY CODE ###

import math
N = 10**5

Q = int(input())


def eratosthenes(n):
    """n以下の素数をエラトステネスの篩によって求める."""
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


primes = eratosthenes(N)

like_2017 = [False] * (10**5 + 1)

for p in primes:
    if (p + 1) // 2 in primes:
        like_2017[p] = True


c = 0
C = [0]
for i in range(1, 10**5 + 1):
    if like_2017[i]:
        c += 1
    C.append(c)


for _ in range(Q):
    left, right = map(int, input().split())
    print(C[right] - C[left - 1])


### FIXED CODE ###

import math
N = 10**5

Q = int(input())


def eratosthenes(n):
    """n以下の素数をエラトステネスの篩によって求める."""
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


_primes = eratosthenes(N)

primes = [False] * (10**5 + 1)

for p in _primes:
    primes[p] = True

like_2017 = [False] * (10**5 + 1)

for p in _primes:
    if primes[(p + 1) // 2]:
        like_2017[p] = True


c = 0
C = [0]
for i in range(1, 10**5 + 1):
    if like_2017[i]:
        c += 1
    C.append(c)


for _ in range(Q):
    left, right = map(int, input().split())
    print(C[right] - C[left - 1])
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    Ch, Cw = LI_()
    Dh, Dw = LI_()
    S = [SS() for _ in range(H)]

    d = ((1, 0), (0, 1), (-1, 0), (0, -1)) 
    dist = [[INF] * W for _ in range(H)]
    que = collections.deque()
    que.append((Ch, Cw, 0))
    dist[Ch][Cw] = 0
    while que:
        cy, cx, cost = que.popleft()
        for dy, dx in d:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == '.' and cost < dist[ny][nx] :
                dist[ny][nx] = cost
                que.appendleft((ny, nx, cost))
        for dy, dx in itertools.product(range(-2, 3), repeat=2):
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == '.' and cost < dist[ny][nx] :
                dist[ny][nx] = cost + 1
                que.append((ny, nx, cost + 1))

    if dist[Dh][Dw] == INF:
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    Ch, Cw = LI_()
    Dh, Dw = LI_()
    S = [SS() for _ in range(H)]

    d = ((1, 0), (0, 1), (-1, 0), (0, -1)) 
    dist = [[INF] * W for _ in range(H)]
    que = collections.deque()
    que.append((Ch, Cw, 0))
    dist[Ch][Cw] = 0
    while que:
        cy, cx, cost = que.popleft()
        for dy, dx in d:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == '.' and cost < dist[ny][nx] :
                dist[ny][nx] = cost
                que.appendleft((ny, nx, cost))
        for dy, dx in itertools.product(range(-2, 3), repeat=2):
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == '.' and cost + 1 < dist[ny][nx] :
                dist[ny][nx] = cost + 1
                que.append((ny, nx, cost + 1))

    if dist[Dh][Dw] == INF:
        print(-1)
    else:
        print(dist[Dh][Dw])

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

def main():
    """"ここに今までのコード"""

n = int(input())
A = [int(a) for a in input().split()]

xor=[0]*60
for i in range(60):
    l=0
    for j in range(n):
        l+=A[j]%2
        A[j]=A[j]//2
    xor[59-i]=l*(n-l)
    
mod=10**9+7
ans=xor[0]
for j in range(60-1):
    ans=((2*ans)+xor[j+1])%mod
print(int(ans)) 

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    """"ここに今までのコード"""
 
n = int(input())
A = [int(a) for a in input().split()]
mod=10**9+7
 
ans=0
for i in range(60):
    l=sum([a%2 for a in A])
    ans=(ans+l*(n-l)*(2**i))%mod
    A=[a//2 for a in A]
    
 
#ans=xor[0]
#for j in range(60-1):
#    ans=((2*ans)+xor[j+1])%mod
print(int(ans)) 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())

abc = [list(map(int, input().split())) for i in range(N)]
tmp = []

for i in range(2**N):
  a, b = 0, 0
  cost = []
  for j in range(N):
    if (i>>j) & 1:
      cost.append(abc[j][2])
      a += abc[j][0]
      b += abc[j][1]
  if a/Ma == b/Mb and sum(cost) > 0:
    tmp.append(sum(cost))
try:
  print(min(tmp))
except ValueError:
  print(-1)
  

### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
table = []
for i in range(N):
  a,b,c = map(int, input().split())
  table.append([a,b,c])
inf = 10**9
dp = [[[inf]*401 for i in range(401)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(1,N+1):
  a,b,c = table[i-1]
  for j in range(401):
    for k in range(401):
      dp[i][j][k] = dp[i-1][j][k]
      if 400>=j-a>=0 and 400>=k-b>=0:
        dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans = 10**9
i = 1
while max(Ma,Mb)*i <= 400:
  ans = min(ans,dp[N][Ma*i][Mb*i])
  i += 1
if ans == 10**9:
  ans = -1
print(ans)
### BUGGY CODE ###

import copy
import numpy as np
n=int(input())
xl=[list(map(int,input().split()))  for i in  range(n)]

cp=copy.deepcopy(xl)
cp=np.array(cp)
cp=cp.T
#xSort = np.sort(cp[0])[::-1]
dict={k: v for v, k in enumerate(cp[0])}
xr=[x+cp[1][dict[x]] for x in cp[0]]
xl=[x-cp[1][dict[x]] for x in cp[0]]
#print(xr)
#print(xl)
xls=sorted(xl, reverse=True)
xrs=[xr[xl.index(x)] for x in xls]
#print("xrs", xrs)
#print("xls", xls)

ans=0
r=10**5+1
for i in range(len(xls)):
  if xrs[i]>r:
    continue
  if xls[i]<=r:
    r=xls[i]
    #print("r",r)
    ans+=1
    
print(ans)

### FIXED CODE ###

import copy
import numpy as np
n=int(input())
xl=[]
for i in range(n):
    x,l = map(int,input().split())
    xl.append([x-l,l+x])
#print(xl)
xl = sorted(xl, key=lambda x: x[0],reverse=True)
#print(xl)

ans=0
r=2*(10**9+1)
for i in range(n):
  if xl[i][1]>r:
    continue
  if xl[i][0]<=r:
    r=xl[i][0]
    #print("r",r)
    ans+=1
print(ans)
### BUGGY CODE ###

s = input()
l = len(s)

def df(s):
  while True:
    if '01' in s or '10' in s:
      s = s.replace('01', '')
      s = s.replace('10', '')
    else:
      break
  return s

if len(s) < 1000:
  print(l - len(df(s)))
else:
  i = l // 4
  sx = df(s[:i]) + df(s[i:i * 2]) \
         + df(s[i * 2:i * 3]) + df(s[i * 3:])
  print(l - len(df(sx)))

### FIXED CODE ###

s = input()
print(2 * min([sum([v == '1' for v in s]), sum([v == '0' for v in s])]))
### BUGGY CODE ###

x, a = map(int, input().split())
print('0') if x < a else print('10')
cons = 10 ** 8
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
primes(cons)

### FIXED CODE ###

x, a = map(int, input().split())
print('0') if x < a else print('10')
### BUGGY CODE ###

K = int(input())
S = input()
MOD = 10**9 + 7

dp = [[0 for j in range(len(S)+1)] for i in range(len(S)+K+1)]
dp[0][0] = 1

for i in range(len(S)+K):
    for j in range(len(S)+1):
        if j == len(S):
            dp[i+1][j] += dp[i][j]*26
            dp[i+1][j] %= MOD
        else:
            dp[i+1][j] += dp[i][j]*25
            dp[i+1][j] %= MOD
            dp[i+1][j+1] += dp[i][j]
            dp[i+1][j+1] %= MOD

print(dp[len(S)+K][len(S)])


### FIXED CODE ###

K = int(input())
S = input()
MOD = 10**9 + 7


def cmb(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


N = 3*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(len(S), len(S)+K+1):
    ans += cmb(i-1, len(S)-1, MOD)*pow(25, i-len(S), MOD) * \
        pow(26, len(S)+K-i, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop
from collections import defaultdict


def update(heap, a, mode=1):
    while heap and abs(a - heap[0][0]) <= K:
        prev, length = heappop(heap)
        dp[a * mode] = max(dp[a * mode], length + 1)
    for key, value in dp.items():
        heappush(heap, (key * mode, value))


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
dp = defaultdict(int)
bigger = [(-A[0], -1)]
smaller = [(A[0], 1)]
for a in A[1:]:
    update(bigger, -a, -1)
    update(smaller, a)
print(max(dp.values()))

### FIXED CODE ###

def update(i, v):
    i += length
    dp[i] = max(v, dp[i])
    while i:
        i //= 2
        dp[i] = max(dp[2 * i], dp[2 * i + 1])


def query(l, r):
    l += length
    r += length
    res = 0
    while l < r:
        if l % 2:
            res = max(dp[l], res)
            l += 1
        l //= 2
        if r % 2:
            res = max(dp[r - 1], res)
            r -= 1
        r //= 2
    return res


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
length = 1 << 20
dp = [0] * (2 * length)
res = 0
for a in A:
    cur = query(max(a - K, 0), min(a + K + 1, 300005))
    res = max(res, cur + 1)
    update(a, cur + 1)
print(res)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
        dp[i]=0
print(dp[n])

### FIXED CODE ###

N,M=map(int,input().split())
B=[1]+[1]+[0]*(N-1)
for j in range(M):
    a=int(input())
    B[a]=-1
    if a==1:
        B[a]=0
i=2
while i<=N:
    if B[i]==-1:
        B[i]=0
    else:
        B[i] = (B[i - 1] + B[i - 2]) % (10 ** 9 + 7)
    i+=1
print(B[N])
### BUGGY CODE ###

x,y=map(int,input().split());ans=0
if x==y:
  print(-1)
else:
  for i in range(2,(x*y//min(x,y))+1):
    if x*i%y!=0:
      print(x*i)
      break
    

### FIXED CODE ###

x, y=map(int, input().split())
print(-1 if x%y==0 else x)
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 10 ** 10
for i in range(n):
  ans = min(ans, s[:i].count("W")+s[i+1:].count("E"))
print(ans)

### FIXED CODE ###

from itertools import accumulate
n = int(input())
s = list(input())
l = [1 if s[i] == "E" else 0 for i in range(n)]
l = list(accumulate(l))
ans = l[-1]-l[0]
for i in range(1, n):
    ans = min(ans, i-l[i-1] + l[-1]-l[i])
print(ans)
### BUGGY CODE ###

n , m = map(int, input().split())

root = []
for i in range(m):
    root.append(list(map(int, input().split())))

#room_li = list(range(1,n+1))

answer_li  = [0]*n

now_li  = [1]

next_now = []

delete_li = []

while True:
    for n in now_li:
        for i, r in enumerate(root):
            if n in r:
                #root.pop(i)
                delete_li.append(i)
                r.remove(n)
                dest = r[0]
                if answer_li[dest-1] == 0:
                    answer_li[dest-1] = n
                next_now.append(dest)
        cnt = 0
        for d in delete_li:
            root.pop(d-cnt)
            cnt += 1
        delete_li = []
    now_li = next_now
    next_now = []

    if len(root) <=1:
        break
answer_li = answer_li[1:]
if 0 not in answer_li:
    print('Yes')
    for i in answer_li:
        print(i)
else:
    print('No')



### FIXED CODE ###

n , m = map(int, input().split())

root = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    root[a-1].append(b)
    root[b-1].append(a)

kakutei = [1]

answer_li = [0]*n

while kakutei:
    k = kakutei.pop(0)
    for r in root[k-1]:
        if answer_li[r-1] == 0:
            kakutei.append(r)
            answer_li[r-1] = k

answer_li = answer_li[1:]
if 0 in answer_li:
    print('No')
else:
    print('Yes')
    for i in answer_li:
        print(i)
### BUGGY CODE ###

import sys
N,A,B=map(int,input().split())
S=[]
for i in range(N):
  S+=[int(input())] 
S.sort(reverse=1)
count=0

def Check(T):
  count=0
  for i in range(N):
    if (S[i]-B*T)/(A-B)%1==0:
      count+=max(0,int((S[i]-B*T)/(A-B)))
    else:
      count+=max(0,int((S[i]-B*T)/(A-B))+1)
  if count<=T:
    return 1
  else:
    return 0

L=1
while True:
  if S[0]/B >=2**L:
    L+=1
  else:
    break

T=2**L#checkしたいナンバー。
for l in range(L,0,-1):
  if Check(T)==1:
    T-=2**(l-1)
  elif Check(T)==0:
    T+=2**(l-1)
if Check(T)==0:
  print(T+1)
else:
  print(T)

### FIXED CODE ###

import math
N,A,B=map(int,input().split())
S=[]
for i in range(N):
  S+=[int(input())] 
S.sort(reverse=1)
count=0

def Check(T):
  count=0
  for i in range(N):
    a=math.ceil((S[i]-B*T)/(A-B))
    if a>0:
      count+=a
    else:
      break
  if count<=T:
    return 1
  else:
    return 0

L=1
while True:
  if S[0]/B >=2**L:
    L+=1
  else:
    break

T=2**L#checkしたいナンバー。
for l in range(L,0,-1):
  if Check(T)==1:
    T-=2**(l-1)
  elif Check(T)==0:
    T+=2**(l-1)
if Check(T)==0:
  print(T+1)
else:
  print(T)
### BUGGY CODE ###

n = int(input())
que = []

for i in range(n):
    lineArr = input().split()
    ope = lineArr[0]

    if ope == 'insert':
        num = int(lineArr[1])
        que.insert(0, num)
    elif ope == 'delete':
        num = int(lineArr[1])
        try:
            que.remove(num)
        except ValueError:
            pass
    elif ope == 'deleteFirst':
        que.pop(0)
    else:
        que.pop()

print(*que)



### FIXED CODE ###

import collections

n = int(input())
que = collections.deque()

for i in range(n):
    line = input()

    if line[0] == 'i':
        que.appendleft(int(line[7:]))
    elif line[6] == ' ':
        try:
            que.remove(int(line[7:]))
        except ValueError:
            pass
    elif line[6] == 'F':
        que.popleft()
    else:
        que.pop()

print(*que)
### BUGGY CODE ###



if __name__ == "__main__":
    n = int(input())
    lst = []
    count = 0
    for i in range(n):
        lst.append(''.join(sorted(input())))
    for i in range(n):
        for j in range(i + 1, n):
            count += int(lst[i] == lst[j])
    print(count)

### FIXED CODE ###

from collections import defaultdict
from math import factorial
if __name__ == "__main__":
    n = int(input())
    lst = []
    count = 0
    words = defaultdict(lambda: 0)
    for i in range(n):
        words[''.join(sorted(input()))] += 1
    sum = 0
    for word in words:
        sum += int(factorial(words[word]) / (factorial(2) * factorial(abs(words[word] - 2))))
    print(sum)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
s2 = list(set(s))
ans = []

for i in s2:
  ans.append([s.count(i),i])
ans.sort()
sai = max(ans)

for i in range(len(ans)):
  if ans[i][0] == sai[0]:
    print(ans[i][1])

### FIXED CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
s = collections.Counter(s)
m = 0
ans = []

for i in s.values():
  m = max(m,i)

for k, j in s.items():
  if j == m:
    ans.append(k)
ans.sort()

for i in range(len(ans)):
  print(ans[i])
#print(*ans, sep = "\n")
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

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

S,T = input(),input()

dp = [[0]*(len(T)+1) for _ 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-1], dp[i-1][j], dp[i-1][j-1] + (S[i-1]==T[j-1]))

res = []
x,y = len(S),len(T)
v = dp[x][y]
while v > 0:
  if dp[x-1][y] == v:
    x -= 1
  elif dp[x][y-1] == v:
    y -= 1
  else:
    res.append(S[x-1])
    x -= 1
    y -= 1

  v = dp[x][y]

print(''.join(reversed(res)))

### FIXED CODE ###

S,T = input(),input()

dp = [[0]*(len(T)+1) for _ 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-1], dp[i-1][j], dp[i-1][j-1] + (S[i-1]==T[j-1]))

res = []
x,y = len(S),len(T)
v = dp[x][y]
while v > 0:
  if dp[x-1][y] == v:
    x -= 1
  elif dp[x][y-1] == v:
    y -= 1
  else:
    res.append(S[x-1])
    x -= 1
    y -= 1

  v = dp[x][y]

print(''.join(reversed(res)))
### BUGGY CODE ###

h, w, a, b = [int(item) for item in input().split()]

MOD = 10**9 + 7
n = 2 * 10**5
def mod_pow(x, n):
    ans = 1
    while(n != 0):
        if n & 1:
            ans = ans * x % MOD
        x = x * x % MOD
        n = n >> 1
    return ans

fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    # Fermat's little theorem says
    # a**(p-1) mod p == 1
    # then, a * a**(p-2) mod p == 1
    # it means a**(p-2) is inverse element
    fac_inv[i] = fac_inv[i-1] * mod_pow(i, MOD-2) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

ans = 0
for i in range(h-a):
    ans += mod_nCr(b-1+i, i) * mod_nCr(w-b-1 + h-1-i, h-1-i)
    ans %= MOD
print(ans)

### FIXED CODE ###

h, w, a, b = [int(item) for item in input().split()]

MOD = 10**9 + 7
n = h + w 
def mod_pow(x, n):
    ans = 1
    while(n != 0):
        if n & 1:
            ans = ans * x % MOD
        x = x * x % MOD
        n = n >> 1
    return ans

fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    # Fermat's little theorem says
    # a**(p-1) mod p == 1
    # then, a * a**(p-2) mod p == 1
    # it means a**(p-2) is inverse element
    fac_inv[i] = fac_inv[i-1] * mod_pow(i, MOD-2) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

if a+b > (h+w)//2:
    ans = 0
    for i in range(h-a):
        ans += mod_nCr(b-1+i, i) * mod_nCr(w-b-1 + h-1-i, h-1-i)
        ans %= MOD
else:
    ans = mod_nCr(h-1+w-1, h-1)
    for i in range(b):
        ans -= mod_nCr(h-a-1+i, i) * mod_nCr(a-1 + w-1-i, a-1)
        ans %= MOD
print(ans)
### BUGGY CODE ###

n,a,b = (int(x) for x in input().split())
mod = 10**9+7

def minus(k):
    x,y =1,1
    for i in range(k):
        x*=(n-i)%mod
        y*=(k-i)%mod
    return x*pow(y, mod-2, mod)%mod

ans = pow(2,n,mod)-1-minus(a)-minus(b)
while ans<0:
    ans+=mod
print(ans%mod)


### FIXED CODE ###

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

def minus(n,k):
    x,y =1,1
    for i in range(k):
        x=x*(n-i)%mod
        y=y*(k-i)%mod
    return x*pow(y, mod-2, mod)%mod

ans = pow(2,n,mod)-1-minus(n,a)-minus(n,b)
while ans<0:
    ans+=mod
print(ans)