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

from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
wx = [2, -2, 0, 0, -1, -1, 1, 1, 1, 2, 2, -1, -2, -2, 1, 2, 2, -1, -2, -2]
wy = [0, 0, 2, -2, -1, 1, -1, 1, 2, 2, 1, -2, -2, -1, -2, -2, -1, 2, 2, 1]
maze = []

for _ in range(H):
    maze.append(list(input()))

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.append((sx, sy, 0))

while q:
    x, y, s = q.pop()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != '#' and d[nx][ny] > s:
            d[nx][ny] = s
            q.append((nx, ny, s))
    for i in range(20):
        nx = x + wx[i]
        ny = y + wy[i]
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != '#' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.append((nx, ny, s+1))

if d[gx][gy] == INF:
    print(-1)
else:
    print(d[gx][gy])


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

import itertools
from sys import stdin
N=int(input())
st=list(stdin.readline().strip())
count=0
cnt=0
num=["0","1","2","3","4","5","6","7","8","9"]

num_list= ["".join(i) for i in itertools.product(num,repeat=3)]

for number in num_list:
    for i in range(N):

        if cnt==0 and number[0]==st[i]:
            cnt+=1
            continue
        if cnt==1 and number[1]==st[i]:
            cnt+=1
            continue
        if cnt==2 and number[2]==st[i]:
            cnt+=1
            break
    if cnt==3:
        count+=1
    cnt=0
print(count)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

from heapq import heappop, heappush

n = int(input())
xd = [list(map(int, input().split())) for _ in range(n)]
mod = 998244353
INF = 10 ** 18

xx = []
for i, (x, d) in enumerate(xd, 1):
    xx.append([i, x, 0])
    xx.append([i, x + d - 0.5, 1])

xx.sort(key=lambda x: x[1])

adj = [[] for _ in range(n + 1)]
now = {0}
hp = [(INF, 0)]
for i, x, remove in xx:
    if remove:
        now.remove(i)

    else:
        while hp[0][1] not in now:
            heappop(hp)

        px, pi = hp[0]
        adj[pi].append(i)

        now.add(i)
        heappush(hp, (-x, i))

stack = [0]
d = [-1] * (n + 1)
d[0] = 0
c = [[] for _ in range(n + 1)]
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            c[u].append(v)
            stack.append(v)

dp = [1] * (n + 1)
for u in order[::-1]:
    for v in c[u]:
        dp[u] *= dp[v]
        dp[u] %= mod

    dp[u] += 1
    dp[u] %= mod

ans = dp[0] - 1
ans %= mod
print(ans)


### FIXED CODE ###

def main():
    n = int(input())
    xd = [map(int, input().split()) for _ in range(n)]
    mod = 998244353
    INF = 10 ** 10

    xx = [(x, x + d, i) for i, (x, d) in enumerate(xd, 1)]
    xx.sort()
    adj = [[] for _ in range(n + 1)]
    stack = [(INF, 0)]
    for l, r, i in xx:
        while stack[-1][0] <= l:
            stack.pop()

        ip = stack[-1][1]
        adj[ip].append(i)
        stack.append((r, i))

    stack2 = [0]
    d = [-1] * (n + 1)
    d[0] = 0
    c = [[] for _ in range(n + 1)]
    order = []
    while stack2:
        u = stack2.pop()
        order.append(u)
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                c[u].append(v)
                stack2.append(v)

    dp = [1] * (n + 1)
    for u in order[::-1]:
        for v in c[u]:
            dp[u] *= dp[v]
            dp[u] %= mod

        dp[u] += 1
        dp[u] %= mod

    ans = dp[0] - 1
    ans %= mod
    print(ans)


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

a,b,c,k=map(int,input().split())
a_arr = [1 for i in range(a)]
b_arr = [0 for i in range(b)]
c_arr = [-1 for i in range(c)]
arr = a_arr + b_arr + c_arr
print(sum(arr[:k]))


### FIXED CODE ###

a,b,c,k=map(int,input().split())
if k <= a:
    print(k)
elif k <= a+b:
    print(a)
else:
    print(2*a-k+b)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    tmp = a[:]
    tmp.pop(i)
    tmp.sort()
    print(tmp[-1])

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
sa = sorted(a)
maxi = sa.count(sa[-1])
ans = sa[-1]
max_index = a.index(sa[-1])
if maxi == 1:
    for i in range(n):
        if i == max_index:
            print(sa[-2])
        else:
            print(ans)
else:
    for i in range(n):
        print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [[] for i in range(n-1)]
for i in range(m):
  s, t = map(int, input().split())
  a[s-1].append(t-1)
dp = [0]*n
sum_d = [0]*(n-1)
max_d = [0]*(n-1)
b = [0]*n
for i in range(n-2,-1,-1):
  for j in a[i]:
    sum_d[i] += dp[j] + 1
    b[i] += 1
    if max_d[i] < dp[j]+1 and len(a[i]) > 1:
      max_d[i] = dp[j]+1  
  dp[i] = sum_d[i] / b[i]
min_dp = dp[0]
for k in range(n-2):
  if b[k]==1:
    continue
  dp[k] = (sum_d[k]-max_d[k]) / (b[k]-1)
  for i in range(k-1,-1,-1):
    dp[i] = sum([dp[j] + 1 for j in a[i]]) / b[i]
  min_dp = min(min_dp,dp[0])
print(min_dp)

### FIXED CODE ###

n, m = map(int, input().split())
a = [[] for i in range(n-1)]
for i in range(m):
  s, t = map(int, input().split())
  a[s-1].append(t-1)
dp = [0]*n
sum_d = [0]*(n-1)
max_d = [0]*(n-1)
b = [0]*n
for i in range(n-2,-1,-1):
  for j in a[i]:
    sum_d[i] += dp[j] + 1
    b[i] += 1
    if max_d[i] < dp[j]+1 and len(a[i]) > 1:
      max_d[i] = dp[j]+1  
  dp[i] = sum_d[i] / b[i]
min_dp = dp[0]
for k in range(n-2):
  if b[k]==1:
    continue
  ddp = [0]*k + [dp[k] - (sum_d[k]-max_d[k])/(b[k]-1)]
  for i in range(k-1,-1,-1):
    ddp[i] = sum([ddp[j] for j in a[i] if j <= k]) / b[i]
  min_dp = min(min_dp,dp[0] - ddp[0])
print(min_dp)
### BUGGY CODE ###

n = int(input())
*a, = sorted(map(int, input().split()))

m = a[0]
while any(map(lambda x: x%m, a)):
    a = sorted([m] + list(map(lambda x: x-m, a[1:])))
    m = a[0]
    if m == 0:
        a = a[1:]
        m = a[0]

print(m)


### FIXED CODE ###

from functools import reduce
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
print(reduce(gcd, a))
### BUGGY CODE ###

import sys


class BinaryIndexedTree:
    def __init__(self, n, MOD):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
        self.MOD = MOD

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s % self.MOD

    def add(self, i, x):
        mod = self.MOD
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % mod
            i += i & -i

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_


n, k, *lr = map(int, sys.stdin.buffer.read().split())
lr = list(zip(lr[0::2], lr[1::2]))
MOD = 998244353

bit = BinaryIndexedTree(n + 2, MOD)
bit.add(1, 1)
for i in range(1, n):
    v = bit.sum(i)
    for l, r in lr:
        bit.add(i + l, v)
        bit.add(min(i + r + 1, n + 1), -v)

print((bit.sum(n) - bit.sum(n - 1)) % MOD)


### FIXED CODE ###

import sys


class BinaryIndexedTree:
    def __init__(self, n, MOD):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
        self.MOD = MOD

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % self.MOD
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % self.MOD
            i += i & -i

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_


n, k, *lr = map(int, sys.stdin.buffer.read().split())
lr = list(zip(lr[0::2], lr[1::2]))
MOD = 998244353

bit = BinaryIndexedTree(n + 2, MOD)
bit.add(1, 1)
for i in range(1, n):
    v = bit.sum(i)
    for l, r in lr:
        bit.add(i + l, v)
        bit.add(min(i + r + 1, n + 1), -v)

print((bit.sum(n) - bit.sum(n - 1)) % MOD)
### BUGGY CODE ###

from sys import exit
import sys

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

_a = -1
B = []
ans = 0
count = 0

for i in range(M):
    a_ = int(input())
    if _a + 1 == a_:
        print(0)
        exit()
    _a = a_
    N -= 2
    count += 1
    B.append(_a + 2 - 2 * count)


step = [1]

for s in range(1, N + 1):
    if s == 1:
        step.append(1)
        continue
    if s in B:
        step.append(step[s - 1])
        continue
    else:
        step.append(step[s - 1] + step[s - 2])

print(step[N] % 1000000007)


### FIXED CODE ###

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

A = [False] * (N + 1)

for _ in range(M):
    A[int(input())] = True

step = [0] * (N + 1)

step[0] = 1

for s in range(1, N + 1):
    if A[s]:
        step[s] = 0
        continue
    if s == 1:
        step[s] = 1
        continue
    else:
        step[s] = step[s - 1] + step[s - 2]
        step[s] %= 1000000007

print(step[N])
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))

a = []
for i in range(N):
  l = [0] * N
  l[i] = 1/2
  if i < N-1:
    l[i+1] = 1/2
  else:
    l[0] = 1/2
  a.append(l)

a = np.array(a)
b = np.array(A)
n = np.linalg.solve(a, b)
ans = []
for i in range(N):
  ans.append(int(n[i]))
print(*ans)

### FIXED CODE ###

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

tmp = 0
for i in range(N//2):
  tmp += A[2*i+1]
  
ans = []
if sum(A) > 2*tmp:
  ans.append(sum(A)-2*tmp)
else:
  ans.append(0)
  
for i in range(N-1):
  ans.append(2*A[i]-ans[-1])
print(*ans)
### BUGGY CODE ###

from collections import deque

A, B, K = input().split()

A = int(A)
B = int(B)
K = int(K)

value = deque()
s = [i for i in range(A, B+1)]

value.extend(s[0:K])
value.extend(s[len(s)-K:len(s)])

num = deque()

for i in range(len(value)):
    if value[i] not in num:
        num.append(value[i])
        print(value[i])

### FIXED CODE ###

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

value = []

if B - A < K or B <= K:
    value.extend([i for i in range(A, B+1)])
    
else:
    value.extend([i for i in range(A, A+K)])
    value.extend([i for i in range(B-K+1, B+1)])    

num = list(set(value))
num.sort()

for i in range(len(num)):
    print(num[i])
### BUGGY CODE ###

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

from fractions import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd, numbers)

ans=[]
for i in range(N):
    B=A.copy()
    del B[i]
    ans.append(gcd_list(B))
    
print(max(ans))    

### FIXED CODE ###

from fractions import gcd
from functools import reduce

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

ans=[]
L={}
L[0]=0
R={}
R[N+1]=0
R[N+2]=0

def gcd2(x,a):
    if x==0:
        return a
    else:
        return gcd(x,a)

for i in  range(N):
    L[i+1]=gcd2(L[i],A[i])
    R[N-i]=gcd2(R[N-i+1],A[-(i+1)])

for i in range(N):
    ans.append(gcd2(L[i],R[i+2]))
print(max(ans))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = a.copy()

for i in range(m):
    b.sort(reverse=True)
    b[0] = b[0]//2
ans = sum(b)
print(ans)

### FIXED CODE ###

# https://juppy.hatenablog.com/entry/2018/11/08/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC_heapq_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3
n, m = map(int, input().split())
a = list(map(int, input().split()))
A = [-int(x) for x in a]

import heapq
heapq.heapify(A)

for i in range(m):
    y = heapq.heappop(A)
    heapq.heappush(A, -(-y//2))
    
print(-sum(A))
### BUGGY CODE ###

import math
def using_sqrt(limit):
    n = 0
    primes = set()
    for k in range(2, limit+1):
        factor = 0
        
        # 2以外の偶数は素数ではないので無視する
        if k % 2 == 0 and k != 2:
            continue
        
        # 繰り返しの上限を対象の平方根にする
        for divisor in range(2, math.floor(math.sqrt(k))+1):
            if k % divisor == 0:
                factor += 1
                
        if factor == 0:
            primes.add(k)
            
    return primes

primes = using_sqrt(10**5)

q = int(input())
for i in range(q):
    l, r = map(int,input().split())
    count = 0
    for j in range(l, r+1, 2):
        count += (j in primes and (j+1)/2 in primes )
    print(count)

### FIXED CODE ###

import math
def using_sqrt(limit):
    n = 0
    primes = set()
    for k in range(2, limit+1):
        factor = 0
        
        # 2以外の偶数は素数ではないので無視する
        if k % 2 == 0 and k != 2:
            continue
        
        # 繰り返しの上限を対象の平方根にする
        for divisor in range(2, math.floor(math.sqrt(k))+1):
            if k % divisor == 0:
                factor += 1
                
        if factor == 0:
            primes.add(k)
            
    return primes

primes = using_sqrt(10**5+1)

likely = []
count = 0
for i in range(10**5+1):
    if i in primes and (i+1)/2 in primes:
        count += 1
    likely.append(count)
        
q = int(input())
    
for i in range(q):
    l, r = map(int,input().split())
    print(likely[r]-likely[l-1])
### BUGGY CODE ###

from __future__ import division
import itertools

def exp(a,b,c,d):
    L=["(%d%c%d)%c(%d%c%d)","%d%c(%d%c(%d%c%d))","((%d%c%d)%c%d)%c%d","%d%c((%d%c%d)%c%\
d)","(%d%c(%d%c%d))%c%d"]
    opr=["+","-","*","/","+","-","*","/","+","-","*","/"]
    for i,j,k,l in itertools.permutations([a,b,c,d]):
        for o1,o2,o3 in itertools.permutations(opr,3):
            for st in L:
                r=st%(i,o1,j,o2,k,o3,l)
                try:
                    t=eval(r)
                    if t==10:
                        return r
                except ZeroDivisionError:
                    pass
    return 0

while True:
    a,b,c,d=map(int,raw_input().split())
    if a==b==c==d==0:break
    print exp(a,b,c,d)

### FIXED CODE ###

from __future__ import division
import itertools

def exp(a,b,c,d):
    L=["((%d%c%d)%c(%d%c%d))","(%d%c(%d%c(%d%c%d)))","((%d%c(%d%c%d))%c%d)","(%d%c((%d%\
c%d)%c%d))","((%d%c(%d%c%d))%c%d)"]
    opr=["+","-","*"]
    for i,j,k,l in itertools.permutations([a,b,c,d]):
        for o1,o2,o3 in itertools.product(opr,repeat=3):
            for st in L:
                r=st%(i,o1,j,o2,k,o3,l)
                try:
                    t=eval(r)
                    if t==10:
                        return r
                except ZeroDivisionError:
                    pass
    return 0

while True:
    a,b,c,d=sorted(map(int,raw_input().split()),reverse=True)
    if a==b==c==d==0:break
    print exp(a,b,c,d)
### BUGGY CODE ###

# 2019/09/01
# AtCoder Beginner Contest 139 - D

# Input
n = int(input())

# Make List
p = n
asum = n % 1
lim = n + 1

for i in range(2, lim):
    p = i - 1
    asum = asum + p % i

# Output
print(asum)


### FIXED CODE ###

# 2020/08/16
# AtCoder Beginner Contest 139 - D

# Input
n = int(input())

# Calc
ans = n * (n-1) // 2

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

A,B,N = map(int,input().split())
ans = []
if N < 15:
    for x in range(N+1):
        tmp = (A * x // B) - A * (x//B)
        ans.append(tmp)
        #print(tmp)
else:
    for x in range(N-10000000,N+1):
        tmp = (A * x // B) - A * (x//B)
        ans.append(tmp)
        #print(tmp)
print(max(ans))

### FIXED CODE ###

A,B,N = map(int,input().split())
if N >= (B-1):
        x = B -1
else:
        x = N
print((A * x // B) - A * (x//B))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    d={}
    c=0
    edge1=[[] for _ in range(N*(N-1)//2)]
    edge2=[[] for _ in range(N*(N-1)//2)]
    for i in range(N):
        l=list(map(lambda x: int(x)-1,input().split()))
        prev=-1
        for x in l:
            if min(i,x)*10**3+max(i,x) in d:
                if prev!=-1:
                    edge1[prev].append(d[min(i,x)*10**3+max(i,x)])
                    edge2[d[min(i,x)*10**3+max(i,x)]].append(prev)
            else:
                d[min(i,x)*10**3+max(i,x)]=c
                if prev!=-1:
                    edge1[prev].append(c)
                    edge2[c].append(prev)
                c+=1
            prev=d[min(i,x)*10**3+max(i,x)]
    stack=[]
    days=[-1]*(N*(N-1)//2)
    for i,l in enumerate(edge2):
        if not l:
            stack.append(i)
            days[i]=1
    if stack:
        for _ in range(3*10**7):
            v=stack.pop()
            for x in edge1[v]:
                if days[x]<days[v]+1:
                    days[x]=days[v]+1
                    stack.append(x)
            if not stack:
                print(max(days))
                exit()
    print(-1)
        

    

        
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=[[] for _ in range(N)]
    for i in range(N):
        A[i]=deque(list(map(lambda x: int(x)-1,input().split())))
    days=1
    c=0
    pre=[]
    tmp=[]
    for i in range(N):
        if A[i] and A[A[i][0]][0]==i:
            tmp.append(i)
            tmp.append(A[i][0])
    tmp=list(set(tmp))
    for i in tmp:
        A[i].popleft()
        c+=1
    pre=tmp
    if c<N*(N-1):
        while c<N*(N-1):
            tmp=[]
            for i in pre:
                if A[i] and A[A[i][0]][0]==i:
                    tmp.append(i)
                    tmp.append(A[i][0])
            tmp=list(set(tmp))
            for i in tmp:
                A[i].popleft()
                c+=1
            pre=tmp
            days+=1
            if days>N*(N-1)//2:
                print(-1)
                exit()
    print(days)
                
            
        
    
        
        

    

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


n = int(raw_input())
stack = []
for i in range(n):
	i = raw_input()
	if "insert" in i:
		try:
		    stack.insert(0, int(i[7:]))
		except:
			pass
	elif "delete " in i and len(stack) > 0:
		try:
		    stack.remove(int(i[7:]))
		except:
			pass
	elif "deleteFirst" in i and len(stack) > 0:
		stack.pop(0)
	elif "deleteLast" in i and len(stack) > 0:
		stack.pop()
if len(stack) > 0:
    print " ".join(map(str, stack))

### FIXED CODE ###

from collections import deque
n = int(raw_input())
stack = deque()
for i in range(n):
	i = raw_input()
	if "insert" in i:
		stack.appendleft(int(i[7:]))
	elif "delete " in i:
		if int(i[7:]) in stack:
		    stack.remove(int(i[7:]))
	elif "deleteFirst" in i:
		stack.popleft()
	elif "deleteLast" in i:
		stack.pop()
print " ".join(map(str, stack))
### BUGGY CODE ###

#abc145_d
import math
m = 10**9+7
x,y = map(int,input().split())

a = max(x,y)
b = min(x,y)
cnt = 0

while a -b-100 >100:
    a -=200
    b -=100
    cnt +=100


while a != b:
    a -= 2
    b -= 1
    cnt +=1

    if a<0 or b <0:
        print(0)
        exit()
if a%3 != 0:
    print(0)
    exit()
else:
    c = a//3

n = (math.factorial(2*c+cnt)%m)*(pow(math.factorial(c+cnt),m-2,m))*(pow(math.factorial(c),m-2,m))
print(n%m)


### FIXED CODE ###

#abc145_d
m = 10**9+7
x,y = map(int,input().split())
fac =[0]*(10**6+1)
a = max(x,y)
b = min(x,y)
cnt = 0
fac[0]=1

while a != b:
    a -= 2
    b -= 1
    cnt +=1
    fac[cnt] = (fac[cnt-1]*cnt)%m

    if a<0 or b <0:
        print(0)
        exit()
c = a//3
d = cnt
if a%3 != 0:
    print(0)
    exit()
    
else:
    while a != 0:
        a -= 1
        b -= 2
        cnt +=1
        fac[cnt] = (fac[cnt-1]*cnt)%m

        a -= 2
        b -= 1
        cnt +=1
        fac[cnt] = (fac[cnt-1]*cnt)%m

n = ((fac[cnt])%m)*(pow(fac[c+d],m-2,m))*(pow(fac[c],m-2,m))
print(n%m)
### BUGGY CODE ###

def div_count(n):
  count = 0
  for v in range(1,n+1):
    if n%v == 0:
    	count += 1
  return count
N = int(input())
sum = 0
for i in range(1,N+1):
  sum += i*div_count(i)

print(sum)

### FIXED CODE ###

N = int(input())

def g(n):
  return ((n**2)+n)//2

goukei = 0
half = N//2
for i in range(1,half+1):
  goukei += i*g(N//i)

add = list(range(half+1,N+1))
goukei += sum(add)
print(goukei)
### BUGGY CODE ###

A, B  = map(int, input().split())
x = list(map(int, input().split()))
inf = float("INF")
dp = [inf]*A
for i in range(A):
    for j in range(A):
        dp[i] = min(dp[i],x[j]+B*min(abs(j-i),abs(A-abs(i-j))))
print(sum(dp))



### FIXED CODE ###

import numpy as np
N, x = map(int, input().split())
a = np.array(list(map(int, input().split())))
b = np.copy(a)
ans = float('inf') 
for i in range(N):
    c = np.roll(a,i)
    b = np.minimum(b,c)
    ans = min(ans, sum(b)+i*x)
print(ans)
### BUGGY CODE ###

N,M=[int(i) for i in input().split()]
a=[]
b=[]
c=[]
flag=False
for i in range(M):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
    if x==1:
        c.append(y)
for i in range(M):
    if b[i]==N:
        flag=a[i] in c

if flag==False:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


### FIXED CODE ###

N,M=[int(i) for i in input().split()]
a=[]
b=[]
c=[]
for i in range(M):
    x,y=[int(i) for i in input().split()]
    if x==1 :
        c.append(y)
    if y==N:
        c.append(x)
if len(c)==len(set(c)):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

mod = 1000000007
n = int(input())
a = list(map(int,input().split()))
import itertools
b = list(itertools.combinations(a, 2))
#print(b)
for i in range(len(b)):
    b[i] = b[i][0]*b[i][1]
print(sum(b)%mod)

### FIXED CODE ###

mod = 1000000007
n = int(input())
a = list(map(int,input().split()))
ans = 0
b = sum(a)
for i in range(n-1):
    b = b-a[i]
    ans += (a[i]*(b))%mod
print(ans%mod)