Harryxun/sft_time huggingface dataset:
### 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()
s = LI()

h = []
for i in range(2**n):
    heappush(h,-s[i])
x = heappop(h)
use = [-x]
for i in range(n):
    tmp2 = []
    for j in use:
        tmp = []
        while h:
            x = heappop(h)
            x = -x
            if j > x:
                tmp2.append(x)
                break
            else:
                tmp.append(x)
        else:
            print('No')
            quit()
        for k in tmp:
            heappush(h,-k)
    use += tmp2
print('Yes')

### 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()
s = LI()
s.sort(reverse=True)
use = [s[0]]
rest = s[1:]
for _ in range(n):
    new_use = []
    que = deque(rest)
    for i in use:
        rest_tmp = []
        while que:
            x = que.popleft()
            if i > x:
                new_use.append(x)
                break
            else:
                rest_tmp.append(x)
        que += rest_tmp
    use += new_use
    use.sort(reverse=True)
    rest = list(que)
    rest.sort(reverse=True)
if len(use) == 2**n:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import queue
import sys 
input=sys.stdin.readline
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    checkVst=[False]*n
    num=[0]*n
    ToVst=queue.Queue()
   
    for i in range(n):
        if checkVst[i]:
            continue
        Vstd=[]
        now=i
        Vstd.append(now)
        checkVst[now]=True

        for kouho in root[now]:
            if checkVst[kouho]:
                continue
            ToVst.put(kouho)
            checkVst[kouho]=True

        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=True
           
            for kouho in root[now]:
                if checkVst[kouho]:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=True
                
        lengh=len(Vstd)
        for v in Vstd:
            num[v]=lengh-1
            num[v]-=len(set(ng[v])&set(Vstd))
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()
    
        

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m,k=map(int,input().split())
uf=UnionFind(n)
block={}
for i in range(n):
    block[i]=[i]
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    block[a-1].append(b-1)
    block[b-1].append(a-1)
    
for i in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
#print(block)
for i in range(n):
    res=uf.size(i)
 #   print(res)
    for value in block[i]:
        if uf.same(value,i):
            res-=1
    ans.append(res)
print(*ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
c = [0]*N

for _ in range(min(K, 100)):
    b = [0]*(N+1)
    for i, a in enumerate(A):
        b[max(i-a, 0)] += 1
        b[min(i+a+1, N)] -= 1
    
    x = 0
    for i in range(N):
        x += b[i]
        A[i] = x

print(" ".join(str(a) for a in A))

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
c = [0]*N

for _ in range(min(K, 100)):
    b = [0]*(N+1)
    for i, a in enumerate(A):
        b[max(i-a, 0)] += 1
        b[min(i+a+1, N)] -= 1
    
    x = 0
    for i in range(N):
        x += b[i]
        A[i] = x

print(" ".join(str(a) for a in A))
### BUGGY CODE ###

import numpy as np
from fractions import gcd
MOD=10**9+7
N,*A=map(int,open(0).read().split())
def lcm(a,b):
  return a*b//gcd(a,b)
s=A[0]
for i in A:
  s=lcm(s,i)
A=np.array(A,dtype=int)
B=s//A
ans=0
for i in B:
  ans=(ans+i)%MOD
print(ans)

### FIXED CODE ###

from fractions import gcd
MOD=10**9+7
N,*A=map(int,open(0).read().split())

def lcm(a,b):
  return a*b//gcd(a,b)
s=1
for i in A:
  s=lcm(s,i)
s%=MOD
ans=0
for i in A:
  ans+=s*pow(i,MOD-2,MOD)
  ans%=MOD
print(ans)
### BUGGY CODE ###

from collections import deque
S=input()
q=int(input())
Q=[]
state=True
ans=deque(S)
for _ in range(q):
    t = input().split()
    if t[0] == "1":
        Q.append(int(t[0]))
    elif t[0] == "2":
        Q.append((int(t[0]),int(t[1]),t[2]))
for que in Q:
    if que == 1:
        state = not state
    else:
        if state:
            if que[1] == 1:
                ans.appendleft(que[2])
            else:
                ans.append(que[2])
        else:
            if que[1] == 2:
                ans.appendleft(que[2])
            else:
                ans.append(que[2])
anss=""
if not state:
    while len(ans) >0:
        anss += ans.pop()
else:
    while len(ans) >0:
        anss += ans.popleft()
print(anss)

### FIXED CODE ###

from collections import deque
S=input()
q=int(input())
Q=[]
state=True
ans=deque(S)
for _ in range(q):
    t = input().split()
    if t[0] == "1":
        Q.append(int(t[0]))
    elif t[0] == "2":
        Q.append((int(t[0]),int(t[1]),t[2]))
for que in Q:
    if que == 1:
        state = not state
    else:
        if state:
            if que[1] == 1:
                ans.appendleft(que[2])
            else:
                ans.append(que[2])
        else:
            if que[1] == 2:
                ans.appendleft(que[2])
            else:
                ans.append(que[2])
anss=""
if not state:
    while len(ans) >0:
        anss += ans.pop()
else:
    while len(ans) >0:
        anss += ans.popleft()
print(anss)
### BUGGY CODE ###

n, k = input().split()
p = input().split()
n = int(n)
k = int(k)
p = [int(p_tmp) for p_tmp in p]

start = 0
max = 0
for i in p[:len(p)-k+1]:
    res = 0.0000000000000
    for j in p[start:start+k]:
        res += 1 + j
    if max < res:
        max = res
    start += 1

print(max/2)
    

### FIXED CODE ###

import queue

n, k = input().split()
p = input().split()
n = int(n)
k = int(k)
p = [int(p_tmp) for p_tmp in p]
q = queue.Queue()

wa = []
max = 0
sum = 0
for i in p:
    i += 1
    sum += i
    q.put(i)
    if q.qsize() > k:
        sum -= q.get()
    
    if q.qsize() == k:
        if max < sum:
            max = sum
        
ans = max
ans /= 2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):
    cnt = 0
    for i in range(0, N):
        flag=True
        for j in range(0, i+1):
            if P[i] > P[j]:
                flag=False
                break
        if flag:
            cnt+=1
    return cnt


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, P))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):
    cnt = 1
    min = P[0]
    for i in range(1, N):
        if P[i] <= min:
            cnt+=1
            min = P[i]
    return cnt


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, P))

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

import sys

def main():
    h, w, m = map(int,input().split())
    bomb = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(m)]
    x = [0] * h
    y = [0] * w

    for h,w in bomb:
        x[h] +=1
        y[w] +=1

    maxX = max(x)
    maxY = max(y)

    r = [h for h,x in enumerate(x) if x == maxX]
    c = [w for w,y in enumerate(y) if y == maxY]

    for ri in r:
        for ci in c:
            if (ri,ci) not in bomb:
                print(maxX + maxY)
                sys.exit()
    print(maxX + maxY -1)
    
main()

### FIXED CODE ###

import sys

def main():
    h, w, m = map(int,input().split())
    bomb = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(m)]
    x = [0] * h
    y = [0] * w

    for h,w in bomb:
        x[h] +=1
        y[w] +=1

    maxX = max(x)
    maxY = max(y)

    r = [h for h,x in enumerate(x) if x == maxX]
    c = [w for w,y in enumerate(y) if y == maxY]

    bomb = set(bomb)
    
    for ri in r:
        for ci in c:
            if (ri,ci) not in bomb:
                print(maxX + maxY)
                sys.exit()
    print(maxX + maxY -1)
    
main()
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k+1):
    if i > s:
        break
    for l in range(k+1):
        if i + l > s:
            break
        for j in range(k+1):
            if i + j + l == s:
                count += 1
                break
print(count) 


### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k+1):
    for l in range(k+1):
        z = s - i - l
        if 0 <= z <= k:
            count += 1

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

# KからDFS -> xからKまでとyからKまで

import sys
sys.setrecursionlimit(10**8)

n = int(input())
graph = [[] for _ in range(n)]
costs = [0 for _ in range(n)]

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

q, k = map(int, input().split())


def dfs(cur, cost, p):
    for g in graph[cur]:
        if g[0] != p and costs[g[0]] == 0:
            costs[g[0]] = g[1] + cost
            dfs(g[0], costs[g[0]], cur)


dfs(k - 1, 0, -1)

for _ in range(q):
    x, y = map(int, input().split())
    print(costs[x-1]+costs[y-1])


### FIXED CODE ###

# disjoint setかと思いきやDFS
# したらTLEになったので根本的にやり方が間違ってるということ
# よくよく考えたらdfsなのでそこにたどり着いたときが最短距離だわ ムダに探索してた


import sys

sys.setrecursionlimit(10000000)

n = int(input())
graph = [[] for _ in range(n)]

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

q, k = map(int, input().split())
k = k - 1
# kからスタートしてぜんぶたどる
ans_list = [0 for _ in range(n)]


def dfs(node, weight):
    for data in graph[node]:
        if not used[data[0]]:
            used[data[0]] = True
            dfs(data[0], weight + data[1])
    ans_list[node] = weight


used = [False for _ in range(n)]
used[k] = True
dfs(k, 0)

for _ in range(q):
    a, b = map(lambda x: int(x) - 1, input().split())
    print(ans_list[a] + ans_list[b])
### BUGGY CODE ###

from heapq import heappush,heappop,heapify

pl = []
pr = []

def f(p):
  res = 0
  s = len(p)
  for i in range(s):
    if p[i][0] > s:
      p[i][0] = -s
    else:
      p[i][0] *= -1
  heapify(p)
  hq = []
  for i in range(s,0,-1):
    #print('p:',p,'i:',i)
    while(len(p) > 0 and p[0][0] == -i):
      a,b = heappop(p)
      heappush(hq,-b)
    #print('hq:',hq)
    if len(hq) > 0:
      b = heappop(hq)
      #print('b:',b)
      res -= b
  return res

def solve():
  ans = 0
  n = int(input())
  for i in range(n):
    k,l,r = map(int,input().split())
    m = min(l,r)
    l -= m
    r -= m
    ans += m
    if l > 0:
      pl.append([k,l])
    else:
      pr.append([n-k,r])
  #print('pl:',pl,'pr:',pr,'ans:',ans)
  ans += f(pl)
  ans += f(pr)
  print(ans)

t = int(input())
for i in range(t):
  solve()

### FIXED CODE ###

from heapq import heappush,heappop,heapify

def f(p):
  res = 0
  s = len(p)
  for i in range(s):
    if p[i][0] > s:
      p[i][0] = s
  p.sort(reverse = True)
  hq = []
  idx = 0
  for i in range(s,0,-1):
    #print('p:',p,'i:',i)
    while(idx < s and p[idx][0] == i):
      heappush(hq,-p[idx][1])
      idx += 1
    #print('hq:',hq)
    if len(hq) > 0:
      res -= heappop(hq)
      #print('res:',res)
  return res

def solve():
  n = int(input())
  pl = []
  pr = []
  ans = 0
  for i in range(n):
    k,l,r = map(int,input().split())
    m = min(l,r)
    l -= m
    r -= m
    ans += m
    if l > 0:
      pl.append([k,l])
    else:
      pr.append([n-k,r])
  #print('pl:',pl,'pr:',pr,'ans:',ans)
  ans += f(pl)
  ans += f(pr)
  print(ans)

t = int(input())
for i in range(t):
  solve()
### BUGGY CODE ###

from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]
for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=[1]

while stack:
    a=stack[-1]
    if not P[a]:
        stack.pop()
        continue
    count=1
    for b in P[a]:
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        P[b].remove(a)
        if P[b]:
            stack.append(b)
        break
    P[a].remove(b)


print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])


### FIXED CODE ###

from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]

for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=deque([1])
delset=set()
while stack:
    #print(C)
    #print(Cpath,"Cpath")
    a=stack[0]
    count=1
    for b in P[a]:
        #b=P[a][-1]
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        stack.append(b)
        #P[a].remove(b)
        P[b].remove(a)
    P[a].clear()
    stack.popleft()

print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])
### BUGGY CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    for i in range(0,100001,2):
        for j in range(-100000,1,1):
            # if i == j:
            #     continue
            if (i-j) * (pow(i,4) + pow(i,3)*j + pow(i,2)*pow(j,2) + i*pow(j,3) + pow(j,4)) == X:
                print(i,j)
                exit()
if __name__ == '__main__':
  main()


### FIXED CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    for i in range(-119,119):
        for j in range(-119,119):
            if i == j:
                continue
            if X % (i - j) == 0:
                if (i-j) * (pow(i,4) + pow(i,3)*j + pow(i,2)*pow(j,2) + i*pow(j,3) + pow(j,4)) == X:
                    print(i,j)
                    exit()
if __name__ == '__main__':
  main()
### BUGGY CODE ###

p = 10**9 + 7
n,m = list(map(int, input().split()))
a = [int(input()) for _ in range(m)]

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

for i in range(n):
    if i+2 not in a:
        dp[i+2] = dp[i]%p
    if i+1 not in a:
        dp[i+1] += dp[i]%p

print(dp[-2]%p)

### FIXED CODE ###

p = 10**9 + 7
n,m = list(map(int, input().split()))
a = set()
for _ in  range(m):
    a.add(int(input()))

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

for i in range(n):
    if i+2 not in a:
        dp[i+2] += dp[i]%p
    if i+1 not in a:
        dp[i+1] += dp[i]%p

print(dp[-2]%p)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
mod = 10**9 + 7
X = []
for i in range(n - 1):
    X.append(x[i + 1] - x[i])
l, left = 1, [1]
for i in range(1, n - 1):
    l *= i
    l %= mod
    left.append(l)
r, right = 1, [1]
for i in range(n - 1, 1, -1):
    r *= i % mod
    right.append(r)
right.reverse()
f, flst = 0, []

for i, j in zip(left, right):
    f += i * j % mod
    f %= mod
    flst.append(f)
s = 0
for i, j in zip(X, flst):
    s += i * j % mod
print(s % mod)


### FIXED CODE ###

# https://atcoder.jp/contests/dwacon6th-prelims/submissions/9426910


def solve():
    MOD = 10**9 + 7

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

    ds = []
    for i in range(N-1):
        d = xs[i+1] - xs[i]
        ds.append(d)

    nums = [1, 1]
    num = 1
    for i in range(2, N-1):
        num *= i
        num %= MOD
        nums.append(num)

    ms = [N-1]
    m = N-1
    for i in reversed(range(2, N-1)):
        m *= i
        m %= MOD
        ms.append(m)
    ms.reverse()
    ms.append(1)

    ks = []
    k = 0
    for num, m in zip(nums, ms):
        k += num*m % MOD
        k %= MOD
        ks.append(k)

    ans = 0
    for d, k in zip(ds, ks):
        ans += d*k % MOD
        ans %= MOD

    print(ans)

solve()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(int(1e7))
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)

memo=[[[-1]*(301) for _ in range(301)] for _ in range(301)]
memo[0][0][0]=0
def c(i,j,k):
        if memo[i][j][k]!=-1:
            return memo[i][j][k]
        else:
            memo[i][j][k]=n/(i+j+k)
            if 0<=i-1<=300:
                memo[i][j][k]+=c(i-1,j,k)*i/(i+j+k)
            if 0<=i+1<=300 and 0<=j-1<=300:
                memo[i][j][k]+=c(i+1,j-1,k)*j/(i+j+k)
            if 0<=j+1<=300 and 0<=k-1<=300:
                memo[i][j][k]+=c(i,j+1,k-1)*k/(i+j+k)
            return memo[i][j][k]

print(c(A,B,C))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)

dp=[[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
def c():
    for k in range(C+1):
        for j in range(B+C+1-k):
            for i in range(n+1-k-j):
                if i==0 and j==0 and k==0:
                    continue
                res=1.0*n
                if i>0:
                    res+=i*dp[i-1][j][k]
                if j>0:
                    res+=j*dp[i+1][j-1][k]
                if k>0:
                    res+=k*dp[i][j+1][k-1]
                dp[i][j][k]=res/(i+j+k)
    print(dp[A][B][C])
c()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a, b= map(int, input().split())

t = [a,b]

r = 0
t_r = []
for i in range(int(10**6/2)):

    l = [i, i*2]

    if l[0] > t[0] or  l[1] > t[1]:
        break

    for j in range(int(10**6/2)):

        l2 = [i + j*2, i*2 + j]
        if l2[0] > t[0] or  l2[1] > t[1]:
            break

        if l2 == t:
            t_r.append([i,j])



for l in t_r:
    r += l[0] + l[1]
print(r)


### FIXED CODE ###

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

def mod_factorial(n):
    mod = 10**9+7

    if n < 1:
        return 1

    r = n
    for i in range(n-1):
        r = r*(i+1) % mod
    
    return r

def mod_pow(n,m):

    mod = 10**9+7
    r = 1

    while m > 0:
        if m & 1:
            r = r*n % mod
        n = n * n % mod
        m = m>>1

    return(r)



def mod_comb(n, k):
    mod = 10**9+7

    if n+k < 1:
        return 1
    
    a = mod_factorial(n)
    b = mod_pow(mod_factorial(k), mod-2)
    c = mod_pow(mod_factorial(n-k), mod-2)


    return (a * ((b * c) % mod)) % mod


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

t = [a,b]

r = 0
mod = 10**9+7

x = (2*a-b)
y = (2*b-a)

if x%3 == 0 and y%3 == 0 and x*y >=0:
    m = int(x/3)
    n = int(y/3)

    r += mod_comb(n+m,m)

print(r)
### BUGGY CODE ###

import math
H, W, A, B = map(int,input().split())
e = 10**9 + 7
def power(a,b):
    if b == 0:
        return 1
    elif b == 1:
        return a % e
    elif b%2 == 0:
        return power(a,b//2)**2 % e
    else:
        return power(a,b//2)**2*a % e
    
M = [1]
N = [1]
for i in range(1,H+W):
    a = M[i-1]*i%e
    M.append(a)
    b = power(M[i],e-2)
    N.append(b)
def c(a,b):
    return M[a+b-2]*N[a-1]*N[b-1]%e

T = 0
for i in range(B+1,W+1):
    P = c(H-A,i)
    Q = c(A,W-i+1)
    T = (T + P*Q)
print(T%e)


### FIXED CODE ###

import math
H, W, A, B = map(int,input().split())
e = 10**9 + 7
def power(a,b):
    if b == 0:
        return 1
    elif b == 1:
        return a % e
    elif b%2 == 0:
        return power(a,b//2)**2 % e
    else:
        return power(a,b//2)**2*a % e
    
M = [1]
for i in range(1,H+W):
    a = M[i-1]*i%e
    M.append(a)
N= [0]*(H+W)
N[H+W-1] = power(M[H+W-1], e-2)
for i in range(H+W-2, -1, -1):
    N[i] = N[i+1] * (i+1) % e

def c(a,b):
    return M[a]*N[b]*N[a-b]%e

T = 0
for i in range(W-B):
    P = c(H+W-A-i-2,H-A-1)
    Q = c(A+i-1,i)
    T = (T + P*Q)
print(T%e)