Problem:


Score : 400 points

Problem Statement

There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.

When the knight is at the square (i, j), it can be moved to either (i+1,j+2) or (i+2, j+1).

In how many ways can the knight reach the square (X, Y)?

Find the number of ways modulo 10^9 + 7.

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

Print the number of ways for the knight to reach (X, Y) from (0, 0), modulo 10^9 + 7.

Sample Input 1

3 3

Sample Output 1

2

There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3).

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

Print the number of ways modulo 10^9 + 7.



Sample input:
3 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
def main():
    
    M = 10**9 + 7
    
    def ncr(n, r, mod=M):
        upp, low = 1, 1
        for i in range(r):
            upp = upp * (n-i) % mod
            low = low * (r-i) % mod
        return upp * pow(low, mod-2, mod) % mod
    
    x, y = map(int, input().split())
    if (x + y) % 3:
        print(0)
        return
    
    n = (x + y) // 3
    
    print(ncr(n, x-n))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
X,Y = map(int,input().split())
mod = 10**9+7

def p(m,n):
  a = 1
  for i in range(n):
    a = (a*(m-i)) % mod
  return a

def c(m,n):
  return p(m,n)*pow(p(n,n),mod-2,mod) % mod

if (X+Y) % 3 == 0 and Y//2 <= X <= Y**2:
  print(c((X+Y)//3,(2*X-Y)//3))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
from functools import reduce


def modcombination(n, k, mod):
    # nCk % mod
    num = reduce(lambda x, y: x * y % mod, range(n, n - k, -1))
    den = reduce(lambda x, y: x * y % mod, range(1, k + 1))
    return num * pow(den, mod - 2, mod) % mod


if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    x, y = map(int, input().split())
    if (x + y) % 3 != 0:
        print(0)
        exit(0)

    m = (2 * x - y) // 3
    n = x - (2 * m)
    if n < 0 or m < 0:
        print(0)
        exit(0)
    if n == 0 or m == 0:
        print(max(n, m))
        exit(0)
    print(modcombination(n + m, n, MOD) % MOD)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
x, y = map(int, input().split())

if not (x + y)%3 == 0:
  print(0)
else:
  m = (2*x - y) / 3
  n = (2*y - x) / 3

  def nCr(n, r):
    fac = 1
    finv = 1
    for i in range(r):
      fac *= n-i
      fac %= MOD
      finv *= i+1
      finv %= MOD
    return fac * pow(finv, MOD-2, MOD) % MOD

  if m-int(m) == 0 and n-int(n) == 0:
    m = int(m)
    n = int(n)
    print(nCr(m+n, n))
  else:
    print(0)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
x, y = map(int, input().split())

m = (2*x - y) / 3
n = (2*y - x) / 3

def nCr(n, r):
  fac = 1
  finv = 1
  for i in range(r):
    fac *= n-i
    fac %= MOD
    finv *= i+1
    finv %= MOD
  return fac * pow(finv, MOD-2, MOD) % MOD

if m-int(m) == 0 and n-int(n) == 0:
  m = int(m)
  n = int(n)
  print(nCr(m+n, n))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
X, Y = map(int, input().split())

import sys
if (-X+2*Y)%3 != 0 or (2*X-Y)%3 != 0:
    print(0)
    sys.exit()
x, y = (-X+2*Y) // 3, (2*X-Y) // 3
P = 1000000007

def mul(a, b):
    return ((a % P) * (b % P)) % P
 
def div(x, y):
    return mul(x, pow(y, P-2, P))
 
def comb(n, r):
    x = 1
    for i in range(n, n - r, -1):
        x = (x * i) % P
        
    y = 1
    for i in range(1, r+1):
        y = (y * i) % P
    return div(x, y)

print(comb(x + y, min(x, y)))

Submission status: Wrong Answer

Solution code:
MOD=10**9+7

def nCr(n,r):
    """組み合わせ"""
    res=1
    fac=1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac, MOD-2, MOD)%MOD

def main():
    X,Y=map(int,input().split())
    if (X+Y)%3!=0:
        print(0)
        exit()
    n=(2*Y-X)//3
    m=(2*X-Y)//3
    print(nCr(n+m,min(n,m)))

main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
X,Y = map(int,input().split())
x = (-X+2*Y) /3
y = (2*X-Y) /3
#ans=0のときをどっかで書く。indentめんどいからどうする？
MOD = 10**9+7
if int(x) == x and int(y) == y and x>0 and y>0 :
  sum1 = int(x+y)
  bunbo = min([int(x),int(y)])
  n1 = reduce(lambda a,b : (a*b) % MOD  ,range(sum1,sum1-bunbo,-1),1)
  n2 = reduce(lambda a,b : (a*b) % MOD ,range(bunbo,1,-1),1)
  print((n1*pow(n2,MOD-2,MOD)) % MOD)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
x, y = map(int, input().split())

from operator import mul
from functools import reduce
def combination_count(n, r):
  r = min(n-r, r)
  num = reduce(modmul, range(n, n-r, -1), 1)
  denom = reduce(modmul, range(r, 1, -1), 1)
  return num*mod_inv(denom,10**9+7)

def modmul(a, b):
  return mul(a,b)%(10**9+7)

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (x+y)%3 != 0:
  print('0')
else:
  m = (2*x - y)//3
  n = x - 2*m
  c = combination_count(m+n, m)
  print(c%(10**9+7))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def nCr(n,r):
  bunshi = 1
  bunbo = 1
  for i in range(r):
    bunshi = (bunshi * (n-i)) % MOD
    bunbo = (bunbo * (i+1)) % MOD
  return bunshi * pow(bunbo, MOD - 2, MOD) % MOD


def main():
  X, Y = map(int, readline().split())
  if (X + Y) % 3 != 0 or (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
    print(0)
    sys.exit()
  else:
    n = (2*Y - X)//3
    m = (2*X - Y)//3
    ans = nCr(n+m, n)
  print(ans%MOD)
  
  
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def nCr(n,r):
  bunshi = 1
  bunbo = 1
  for i in range(r):
    bunshi = (bunshi * (n-i)) % MOD
    bunbo = (bunbo * (i+1)) % MOD
  return bunshi * pow(bunbo, MOD - 2, MOD) % MOD


def main():
  X, Y = map(int, readline().split())
  if (X+Y)%3 != 0:
    ans = 0
  else:
    n = (2*Y - X)//3
    m = (2*X - Y)//3
    ans = nCr(n+m, n)
  print(ans%MOD)
  
  
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def nCr(n,r):
  bunshi = 1
  bunbo = 1
  for i in range(r):
    bunshi = (bunshi * (n-i)) % MOD
    bunbo = (bunbo * (i+1)) % MOD
  return bunshi * pow(bunbo, MOD - 2, MOD) % MOD


def main():
  X, Y = map(int, readline().split())
  if (X+Y)%3 != 0:
    ans = 0
  else:
    n = (2*Y - X)//3
    m = (2*X - Y)//3
    ans = nCr(n+m, n)
  print(ans)
  
  
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
def pow_mod(n, m, mod):
    if m == 0:
        return 1
    if m == 1:
        return n

    res = 1
    if m % 2 == 1:
        res = n

    return ((pow_mod(n * n % mod, m // 2, mod) % mod) * res) % mod


def frac_mod(n, mod):
    ans = 1
    for i in range(1, n + 1):
        ans = (ans * i) % mod
    return ans


def cmb_mod(n, r, mod):

    mul1 = frac_mod(n, mod) % mod
    mul2 = pow_mod(frac_mod(r, mod), mod - 2, mod) % mod
    mul3 = pow_mod(frac_mod(n - r, mod), mod - 2, mod) % mod

    return (((mul1 * mul2) % mod) * mul3) % mod


x, y = map(int, input().split())

if (x + y) % 3 != 0 or (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(0)
    exit(0)


mod = 10 ** 9 + 7
a = (2 * y - x) // 3
b = (2 * x - y) // 3

print(cmb_mod(a + b, a, mod))

Submission status: Wrong Answer

Solution code:
def pow_mod(n, m, mod):
    if m == 0:
        return 1
    if m == 1:
        return n

    res = 1
    if m % 2 == 1:
        res = n

    return ((pow_mod(n * n % mod, m // 2, mod) % mod) * res) % mod


def frac_mod(n, mod):
    ans = 1
    for i in range(1, n + 1):
        ans = (ans * i) % mod
    return ans


def cmb_mod(n, r, mod):

    mul1 = frac_mod(n, mod) % mod
    mul2 = pow_mod(frac_mod(r, mod), mod - 2, mod) % mod
    mul3 = pow_mod(frac_mod(n - r, mod), mod - 2, mod) % mod

    return (((mul1 * mul2) % mod) * mul3) % mod


x, y = map(int, input().split())

if (x + y) % 3 != 0 or (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(-1)
    exit(0)


mod = 10 ** 9 + 7
a = (2 * y - x) // 3
b = (2 * x - y) // 3

print(cmb_mod(a + b, a, mod))

Submission status: Wrong Answer

Solution code:
def cmb(n, r, p):
    return fact[n] * factinv[r] * factinv[n-r] % p
X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    result = 0
p = 10 ** 9 + 7
n = 7*10**5  # N は必要分だけ用意する
N = 2*n
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    if i <= n:
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)

else:
    result = cmb((X+Y)//3, Y-(X+Y)//3, p)
print(result)

Submission status: Wrong Answer

Solution code:
def cmb(n, r, p):
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
n = 7*10**5  # N は必要分だけ用意する
N = 2*n
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    if i <= n:
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)
    
X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    result = 0
else:
    result = cmb((X+Y)//3, Y-(X+Y)//3, p)
print(result)

Submission status: Wrong Answer

Solution code:
X,Y=map(int,input().split())
P=10**9+7

def fac(n,k,p):
    ans=1
    for i in range(n-k+1,n+1):
        ans=(ans*i)%p
    return ans

def makeinv(length,p):
    L=[0,1]
    for i in range(2,length+1):
        x=p-((L[p%i]*(p//i))%p)
        L.append(x)
    return L

def comb(n,k,p):
    if k==0:
        return 1
    else:
        ans=fac(n,k,p)
        inv=makeinv(k,p)
        for i in range(1,k+1):
            ans=(ans*inv[i])%p
        return ans


if (X+Y)%3!=0:
    print(0)
else:
    N=(X+Y)//3
    K=(2*Y-X)//3
    print(comb(N,K,P))

Submission status: Wrong Answer

Solution code:
X,Y=map(int,input().split())
P=10**9+7

def fac(n,k,p):
    ans=1
    for i in range(n-k+1,n+1):
        ans=(ans*i)%p
    return ans

def makeinv(length,p):
    L=[0,1]
    for i in range(2,length+1):
        x=p-((L[p%i]*(p//i))%p)
        L.append(x)
    return L

def comb(n,k,p):
    ans=fac(n,k,p)
    inv=makeinv(k,p)
    for i in range(1,k+1):
        ans=(ans*inv[i])%p
    return ans


if (X+Y)%3!=0:
    print(0)
else:
    N=(X+Y)//3
    K=(2*Y-X)//3
    print(comb(N,K,P))

Submission status: Wrong Answer

Solution code:
def cmb(n, r, p):
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
n = 4*10**5  # N は必要分だけ用意する
N = 2*n
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    if i <= n:
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)
    
X, Y = map(int, input().split())
if (X+Y)//3 != 0:
    result = 0
else:
    result = cmb((X+Y)//3, Y-(X+Y)//3, p)
print(result)

Submission status: Wrong Answer

Solution code:
def cmb(n, r, p):
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
n = 4*10**5  # N は必要分だけ用意する
N = 2*n
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    if i <= n:
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)
    
X, Y = map(int, input().split())
if X+Y//3 != 0:
    result = 0
else:
    result = cmb((X+Y)//3, Y-(X+Y)//3, p)
print(result)

Submission status: Wrong Answer

Solution code:
def cmb(n, r, p):
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
n = 4*10**5  # N は必要分だけ用意する
N = 2*n
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    if i <= n:
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)
    
X, Y = map(int, input().split())
if X+Y//3 != 0:
    result = 0
else:
    result = cmb((X+Y)//3, Y-(X+Y)//3)
print(result)

Submission status: Wrong Answer

Solution code:
def cmb(n, r, p):
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
n = 4*10**5  # N は必要分だけ用意する
N = 2*n
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    if i <= n:
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)
    
X, Y = map(int, input().split())
a = 0
b = 0
work = X//3 if X//3 < Y//3 else Y//3
a += work
b += work
X -= work*3
Y -= work*3
result = 0
if Y == 2*X:
    a += X
    result = cmb(a+b, a, p)
elif X == 2*Y:
    b += Y
    result = cmb(a+b, a, p)
print(result)

Submission status: Wrong Answer

Solution code:
def fact(n,mod):
    ret=1
    for i in range(2,n+1):
        ret=(ret*i)%mod
    return ret

def pCq(p,q,mod):
  pCq=1
  for i in range(q):
    pCq*=p-i
    pCq=pCq%mod
  den=fact(q,mod)
  inv=pow(den,mod-2,mod)
  pCq=(pCq*inv)%mod
  return pCq

X,Y=map(int,input().split())
MOD=10**9+7
ans=0
n,m=2*X-Y,2*Y-X
if n%3==0 and m%3==0:
  n//=3
  m//=3
  ans=pCq(m+n,min(m,n),MOD)
print(ans)

Submission status: Wrong Answer

Solution code:
def fact(n,mod):
  ret=1
  for i in range(2,n+1):
    ret=(ret*i)%mod
  return ret

def pCq(p,q,mod):
  pCq=1
  for i in range(q):
    pCq*=p-i
    pCq=pCq%mod
  den=fact(q,mod)
  inv=pow(den,mod-2,mod)
  pCq=(pCq*inv)%mod
  return pCq

X,Y=map(int,input().split())
MOD=10**9+7
ans=0
n,m=2*X-Y,2*Y-X
if n%3==0 and m%3==0:
  n//=3
  m//=3
  ans+=pCq(m+n,min(m,n),MOD)
print(ans)

Submission status: Wrong Answer

Solution code:
def fact(n,mod):
  ret=1
  for i in range(2,n+1):
    ret=(ret*i)%mod
  return ret

def pCq(p,q,mod):
  pCq=1
  for i in range(q):
    pCq*=p-i
    pCq=pCq%mod
  den=fact(q,mod)
  inv=pow(den,mod-2,mod)
  pCq=(pCq*inv)%mod
  return pCq

X,Y=map(int,input().split())
MOD=10**9+7
ans=0
n,m=2*X-Y,2*Y-X
if n%3==0 and m%3==0:
  n//=3
  m//=3
  ans+=pCq(m+n,m,MOD)
print(ans)

Submission status: Wrong Answer

Solution code:
def fact(n,mod):
  ret=1
  for i in range(2,n+1):
    ret=(ret*i)%mod
  return ret

def pCq(p,q,mod):
  pCq=1
  for i in range(q):
    pCq*=p-i
    pCq=pCq%mod
    den=fact(q,mod)
    inv=pow(den,mod-2,mod)
    pCq=(pCq*inv)%mod
  return pCq

X,Y=map(int,input().split())
MOD=10**9+7
ans=0
n,m=2*X-Y,2*Y-X
if n%3==0 and m%3==0:
  n//=3
  m//=3
  ans+=pCq(m+n,m,MOD)
print(ans)

Submission status: Wrong Answer

Solution code:
# ABC145 - Virtual
# A
if False: print(int(input())**2)

# B
if False:
    N=int(input())
    S=input()
    print('Yes' if N%2==0 and S[:N//2]*2==S else 'No')
# C
if False:
    import itertools

    def fact(n,mod):
        ret=1
        for i in range(2,n+1):
            ret=(ret*i)%mod
        return ret

    N=int(input())
    X=[tuple(map(int,input().split())) for _ in range(N)]
    ans=0
    for p in itertools.permutations(X):
        # print(p)
        sx,sy=p[0]
        for x,y in p:
            ans+=((sx-x)**2+(sy-y)**2)**0.5
            sx,sy=x,y
        # print(ans)
    ans/=fact(N,10**9+7)
    print(ans)

# D
if True:

    def fact(n,mod):
        ret=1
        for i in range(2,n+1):
            ret=(ret*i)%mod
        return ret

    def pCq(p,q,mod):
        pCq=1
        for i in range(q):
            pCq*=p-i
            pCq=pCq%mod
        den=fact(q,mod)
        inv=pow(den,mod-2,mod)
        pCq=(pCq*inv)%mod
        return pCq
    
    X,Y=map(int,input().split())
    MOD=10**9+7
    ans=0
    n,m=2*X-Y,2*Y-X
    if n%3==0 and m%3==0:
        n//=3
        m//=3
        ans+=pCq(m+n,m,MOD)
    print(ans if not(X==Y==0) else 1)
# E

Submission status: Wrong Answer

Solution code:
# ABC145 - Virtual
# A
if False: print(int(input())**2)

# B
if False:
    N=int(input())
    S=input()
    print('Yes' if N%2==0 and S[:N//2]*2==S else 'No')
# C
if False:
    import itertools

    def fact(n,mod):
        ret=1
        for i in range(2,n+1):
            ret=(ret*i)%mod
        return ret

    N=int(input())
    X=[tuple(map(int,input().split())) for _ in range(N)]
    ans=0
    for p in itertools.permutations(X):
        # print(p)
        sx,sy=p[0]
        for x,y in p:
            ans+=((sx-x)**2+(sy-y)**2)**0.5
            sx,sy=x,y
        # print(ans)
    ans/=fact(N,10**9+7)
    print(ans)

# D
if True:
    
    def fact(n,mod):
        ret=1
        for i in range(2,n+1):
            ret=(ret*i)%mod
        return ret

    def pCq(p,q,mod):
        pCq=1
        for i in range(q):
            pCq*=p-i
            pCq=pCq%mod
        den=fact(q,mod)
        inv=pow(den,mod-2,mod)
        pCq=(pCq*inv)%mod
        return pCq
    
    X,Y=map(int,input().split())
    MOD=10**9+7
    ans=0
    n,m=2*X-Y,2*Y-X
    if n%3==0 and m%3==0:
        n//=3
        m//=3
        ans+=pCq(m+n,m,MOD)
    print(ans)
# E

Submission status: Wrong Answer

Solution code:
x, y = map(int, input().split())

from operator import mul
from functools import reduce
def combination_count(n, r):
  r = min(n-r, r)
  num = reduce(modmul, range(n, n-r, -1), 1)
  denom = reduce(modmul, range(r, 1, -1), 1)
  return num*pow(denom, 10**9+5, 10**9+7)

def modmul(a, b):
  return mul(a,b)%(10**9+7)

def modinv(a, b):
  d, x, y = extgcd(a, b)
  return (d + x%b) % b

def gcd(a, b):
  if (b==0):
    return a
  else:
    return gcd(b, a%b)

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]


if (x+y)%3 != 0:
  print('0')
else:
  m = (2*x - y)//3
  n = x - 2*m
  c = combination_count(m+n, m)
  print(c%(10**9+7))

Submission status: Wrong Answer

Solution code:
def comb(n, k, mod):
    if k == 0:
        return 1
    else:
        x, y = n, k
        for i in range(1, k):
            x = x * (x - i) % mod
            y = y * (y - i) % mod
        c = x * pow(y, mod - 2, mod) % mod
        return c


x, y = map(int, input().split())
mod = 10 ** 9 + 7
n = (x + y) // 3
if (x + y) % 3 != 0 or not (n <= x <= 2 * n):
    ans = 0
else:
    k = min(x - n, 2 * n - x)
    ans = comb(n, k, mod)
print(ans)

Submission status: Wrong Answer

Solution code:
#ABC145D

MOD = 10 ** 9 + 7
import math
x,y = map(int,input().split())
a,b = -1,-1

for i in range(x):
    m = 0
    if (x-i) % 2 == 0:
        m = (x-i) // 2
        if 2*i + m == y:
            if i >= 0 and m >= 0:
                a = i
                b = m
                break
    else:
        continue
MAX_N = 10**6

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%MOD)

fact_inv[-1] = pow(fact[-1],MOD-2,MOD)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

def com(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod  
        
        
if a == -1 and b == -1:
    print(0)
else:
    print(com(a+b,a,MOD))

Submission status: Wrong Answer

Solution code:
x, y = map(int, input().split())
MOD = 10 ** 9 + 7

if (x+y) % 3 != 0:
    print(0)
    exit()

#m: (i+2, j+1), n (i+1, j+2)

m = (2*x - y) / 3
n = (2*y - x) / 3

if m < 0 or n < 0:
    print(0)
    exit()

nume = 1
ans = 1
i = 1

while i <= n:
    nume *= m+i
    nume %= MOD
    ans *= nume * pow(i, MOD-2, MOD)
    ans %= MOD
    i += 1

print(int(ans))

Submission status: Wrong Answer

Solution code:
class MathUtil:
    # calculate {m+n}C{n}
    def egcd(self, a: int, b: int):
        if a == 0:
            return b, 0, 1
        else:
            g, y, x = self.egcd(b % a, a)
            return g, x - (b // a) * y, y

    def modinv(self, a: int, m: int):
        g, x, y = self.egcd(a, m)
        if g != 1:
            raise Exception('modular inverse does not exist')
        else:
            return x % m

    def combination(self, n: int, r: int, mod: int = 10**9+7) -> int:
        r = min(r, n-r)
        res = 1
        for i in range(r):
            res = res * (n-i) * self.modinv(i+1, mod) % mod
        return res


x, y = map(int, input().split())


m = - x + 2*y
n = 2*x - y

if m % 3 != 0 or n % 3 != 0:
    print(0)
else:
    m //= 3
    n //= 3

    print(MathUtil().combination(m+n, n))

Submission status: Wrong Answer

Solution code:
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


def combination(n, r, mod=10**9+7):
    """
    nCr mod m
    """
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    exit()

n = (x + y) // 3
a = y - n

print(combination(n, a))

Submission status: Wrong Answer

Solution code:
M=10**9+7
x,y=map(int,input().split())
d,m=divmod(x+y,3)
if m: print(0); exit()
x-=d
y-=d
s=t=1
for i in range(min(x,y)):
  s=s*(x+y-i)%M
  t=t*(i+1)%M
print(s*pow(t,M-2,M)%M)

Submission status: Wrong Answer

Solution code:
def sq(a, b, mod):  # aのb乗を剰余
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod
  
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def nCk(n,k,mod):
  prev=1
  for i in range(1,min(k,n-k)+1):
    v=(prev * (n+1-i) % mod * modinv(i, mod) % mod)
    prev=v
  return prev%mod

x,y=map(int,input().split())
mod=10**9+7

if (x+y)%3!=0:
  print(0)
else:
  n=(x+y)//3
  k=(2*x-y)//3
  print(nCk(n,k,mod))

Submission status: Wrong Answer

Solution code:
def sq(a, b, mod):  # aのb乗を剰余
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod
  
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def nCk(n,k,mod):
  prev=1
  for i in range(1,min(k,n-k)+1):
    v=(prev * (n+1-i) % mod * modinv(i, mod) % mod)
    prev=v
  return prev

x,y=map(int,input().split())
mod=10**9+7

if (x+y)%3!=0:
  print(0)
else:
  n=int((x+y)/3)
  k=int((2*x-y)/3)
  print(nCk(n,k,mod))

Submission status: Wrong Answer

Solution code:
def sq(a, b, mod):  # aのb乗を剰余
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod
  
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def nCk(n,k,mod):
  prev=1
  for i in range(1,min(k,n-k)+1):
    v=(prev * (n+1-i) % mod * modinv(i, mod) % mod)
    prev=v
  return prev

x,y=map(int,input().split())
mod=10**9+7

if (x+y)%3!=0:
  print(0)
else:
  n=(x+y)//3
  k=(2*x-y)//3
  print(nCk(n,k,mod))

Submission status: Wrong Answer

Solution code:
X, Y = map(int, input().split())
if (-X+2*Y)%3 != 0 or (2*X-Y)%3 != 0:
    print(0)
else:
    m = (-X+2*Y) // 3
    n = (2*X-Y) // 3
    if m < 1 or n < 1:
        print(0)
    else:
        mod = 10**9+7
        
        def modinv(a, mod):
            b = mod
            u = 1
            v = 0
            while(b):
                t = a // b
                a -= t * b
                a, b = b, a
                u -= t * v
                u, v = v, u
            
            u %= mod
            return u
    
    
        def modcmb(n, r, mod):
            X = 1
            for i in range(n-r+1, n+1):
                X = X * i % mod
            
            Y = 1
            for i in range(1, r+1):
                Y = Y * i % mod
                
            res = X * modinv(Y, mod) % mod
            return res
        
        print(modcmb(m+n, min(m, n), mod))

Submission status: Wrong Answer

Solution code:
X, Y = map(int, input().split())
if (-X+2*Y)%3 != 0 or (2*X-Y)%3 != 0:
    print(0)
else:
    m = (-X+2*Y) // 3
    n = (2*X-Y) // 3
    mod = 10**9+7
    
    def modinv(a, mod):
        b = mod
        u = 1
        v = 0
        while(b):
            t = a // b
            a -= t * b
            a, b = b, a
            u -= t * v
            u, v = v, u
        
        u %= mod
        return u


    def modcmb(n, r, mod):
        X = 1
        for i in range(n-r+1, n+1):
            X = X * i % mod
        
        Y = 1
        for i in range(1, r+1):
            Y = Y * i % mod
            
        res = X * modinv(Y, mod) % mod
        return res
    
    print(modcmb(m+n, min(m, n), mod))

Submission status: Wrong Answer

Solution code:
from math import factorial

X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if (X + Y) % 3 != 0 or not n.is_integer() or not m.is_integer():
    print(0)
    exit()
    
n, m = map(int, [n, m])
mod = 10**9 + 7
fact = [1]
inv = [1]
for i in range(1, X + Y + 1):
    fact.append((fact[i-1] * i) % mod)
    inv.append(pow(fact[-1], mod-2, mod))

def cmb(n, r):
    return fact[n] * inv[n-r] * inv[r]

print(cmb(n+m, min(n, m)) % mod)

Submission status: Wrong Answer

Solution code:
x,y=map(int,input().split())
a=(2*x-y)/3
b=(-x+2*y)/3
if (2*x-y)%3!=0:
    print(0)
    exit()
a=int(a)
b=int(b)
if a<0 or b<0:
  print(0)
  exit()
mod=10**9+7
if a==0 or b==0:
  print((a+b)%mod)
  exit()
def comb(x,y):
    s=1
    t=1
    for i  in range(0,y):
        s=(s*(x-i))%mod
    for j  in range(1,y+1):
        t=(t*j)%mod
    return (s*pow(t,mod-2,mod))%mod
print(comb(a+b,a))

Submission status: Wrong Answer

Solution code:
x,y=map(int,input().split())
a=(2*x-y)/3
b=(-x+2*y)/3
if (2*x-y)%3!=0:
    print(0)
    exit()
a=int(a)
b=int(b)
if a<0 or b<0:
  print(0)
  exit()
mod=10**9+7
if a==0 or b==0:
  print((a+b)%mod)
  exit()
def comb(x,y):
    s=1
    t=1
    for i  in range(0,y):
        s=(s*(x-i))%mod
    for j  in range(1,y+1):
        t=(t*j)%mod
    return (s*pow(t,mod-2,mod))%mod
print(comb(a+b,min(a,b)))

Submission status: Wrong Answer

Solution code:
x,y=map(int,input().split())
a=(2*x-y)/3
b=(-x+2*y)/3
if (2*x-y)%3!=0:
    print(0)
    exit()
a=int(a)
b=int(b)
if a<0 or b<0:
  print(0)
  exit()
mod=10**9+7
if a==0 or b==0:
  print((a+b)%mod)
  exit()
def comb(x,y):
    s=x
    t=1
    for i  in range(1,y):
        s=(s*(x-i))%mod
    for j  in range(1,y+1):
        t=(t*j)%mod
    return (s*pow(t,mod-2,mod))%mod
print(comb(a+b,min(a,b)))

Submission status: Wrong Answer

Solution code:
x,y=map(int,input().split())
a=(2*x-y)/3
b=(-x+2*y)/3
if (2*x-y)%3!=0:
    print(0)
    exit()
a=int(a)
b=int(b)
mod=10**9+7
def comb(x,y):
    s=x
    t=1
    for i  in range(1,y):
        s=(s*(x-i))%mod
    for j  in range(1,y+1):
        t=(t*j)%mod
    return (s*pow(t,mod-2,mod))%mod
print(comb(a+b,min(a,b)))

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
if (2*b-a)%3==0 and (2*a-b)%3==0 and (2*b-a)>0 and (2*a-b)>0:
  n=(2*b-a)//3
  m=(2*a-b)//3
  p = 10**9+7
  def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % p
            b = b * (r - i) % p
        return (a * pow(b,p-2,p)) % p

  print(nCr((m+n),m))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
if (2*b-a)%3!=0 or (2*a-b)%3!=0:
  print(0)
else:
  n=(2*b-a)//3
  m=(2*a-b)//3
  p = 10**9+7
  def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % p
            b = b * (r - i) % p
        return (a * pow(b,p-2,p)) % p

  print(nCr((m+n),m))

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
if (2*b-a)%3!=0 or (2*a-b)%3!=0:
  print(0)
n=(2*b-a)//3
m=(2*a-b)//3
p = 10**9+7
def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % p
            b = b * (r - i) % p
        return (a * pow(b,p-2,p)) % p

print(nCr((m+n),m))

Submission status: Wrong Answer

Solution code:
x,y=map(int,input().split())
n=(2*y-x)//3
m=(2*x-y)//3
t=min(m,n)
T=1
for i in range(t):
  T*=m+n-i
S=1
for i in range(1,t+1):
  S*=i
print(T//S)