Problem:


Score : 1400 points

Problem Statement

Snuke is having another barbeque party.

This time, he will make one serving of Skewer Meal.

He has a stock of N Skewer Meal Packs. The i-th Skewer Meal Pack contains one skewer, A_i pieces of beef and B_i pieces of green pepper.
All skewers in these packs are different and distinguishable, while all pieces of beef and all pieces of green pepper are, respectively, indistinguishable.

To make a Skewer Meal, he chooses two of his Skewer Meal Packs, and takes out all of the contents from the chosen packs, that is, two skewers and some pieces of beef or green pepper.
(Remaining Skewer Meal Packs will not be used.)
Then, all those pieces of food are threaded onto both skewers, one by one, in any order.

(See the image in the Sample section for better understanding.)

In how many different ways can he make a Skewer Meal? Two ways of making a Skewer Meal is different if and only if the sets of the used skewers are different, or the orders of the pieces of food are different.
Since this number can be extremely large, find it modulo 10^9+7.

Constraints

2≦N≦200,000

1≦A_i≦2000, 1≦B_i≦2000

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
:
A_N B_N

Output

Print the number of the different ways Snuke can make a serving of Skewer Meal, modulo 10^9+7.

Sample Input 1

3
1 1
1 1
2 1

Sample Output 1

26

The 26 ways of making a Skewer Meal are shown below.
Gray bars represent skewers, each with a number denoting the Skewer Meal Set that contained the skewer.
Brown and green rectangles represent pieces of beef and green pepper, respectively.



Sample input:
3
1 1
1 1
2 1


Sample output:
26

Submission status: Wrong Answer

Solution code:
from scipy.special import comb
MOD = 1000000007
#n = 3
#a = [1,1,2]
#b = [1,1,1]
n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
count = 0
for i in range(n-1):
    M = a[i] + b[i]
    for j in range(i+1, n):
        N =  M + a[j] + b[j]
        # print(i+1, j+1, comb(a[i] + b[i] + a[j] + b[j], a[i] + a[j], True))
        count += comb(N, M, True) % MOD
        count = count % MOD
print(count)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

import numpy as np


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


n = int(sys.stdin.buffer.readline())
mp = map(int, sys.stdin.buffer.read().split())
ab = list(zip(mp, mp))
atob = defaultdict(list)
max_a, max_b = 0, 0
for a, b in ab:
    atob[a].append(b)
    max_a = max(max_a, a)
    max_b = max(max_b, b)

MOD = 10 ** 9 + 7

dp = np.zeros(max_b * 2 + 1, dtype=np.int64)
ans = 0
for i in range(-max_a, max_a + 1):
    if i < 0 and -i in atob:
        for j in atob[-i]:
            dp[-j + max_b] += 1
    dp = np.add.accumulate(dp) % MOD
    if i > 0 and i in atob:
        for j in atob[i]:
            ans = (ans + dp[j + max_b]) % MOD

facts, invs = prepare(2 * (max_a + max_b), MOD)
ans = int(ans)
for a, b in ab:
    ans = (ans - facts[2 * (a + b)] * invs[2 * a] * invs[2 * b]) % MOD

print(ans // 2)

Submission status: Wrong Answer

Solution code:
U = 10**6
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
  fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U],MOD-2,MOD)
 
for i in range(U,0,-1):
  fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def comb(n,k):
  if k < 0 or k > n:
    return 0
  z = fact[n]
  z *= fact_inv[k]
  z %= MOD
  z *= fact_inv[n-k]
  z %= MOD
  return z

n = int(input())
ab = [ list(map(int, input().split())) for _ in range(n) ]
ans = 0
for i in range(n-1):
  for j in range(i+1, n):
    ai, bi = ab[i]
    aj, bj = ab[j]
    ans += comb(ai+bi+aj+bj, ai+aj)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 + 7

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

D = 2000

U = 10 ** 4
fact = [1] * U
for n in range(1,U):
    fact[n] = fact[n-1] * n % MOD
fact_inv = [1] * U
fact_inv[-1] = pow(fact[-1],MOD-2,MOD)
for n in range(U-1,0,-1):
    fact_inv[n-1] = fact_inv[n] * n % MOD

C_to_A = [[] for _ in range(D+D+1)]
remove = 0
for a,b in AB:
    c = a+b
    C_to_A[c].append(D-a)
    remove += fact[c+c] * fact_inv[a+a] * fact_inv[b+b]

dp = np.zeros(D+D+1,np.int64)
for A in C_to_A[::-1]:
    dp[1:] += dp[:-1].copy()
    np.add.at(dp,A,1)
    dp %= MOD

x = (dp * dp[::-1] % MOD).sum() % MOD
x -= remove
x *= fact_inv[2]
x %= MOD

print(x)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 + 7

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

D = 2000

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

fact,fact_inv = make_fact(10 ** 4,MOD)
fact = fact.tolist()
fact_inv = fact_inv.tolist()

C_to_A = [[] for _ in range(D+D+1)]
remove = 0
for a,b in AB:
    c = a+b
    C_to_A[c].append(D-a)
    remove += fact[c+c] * fact_inv[a+a] * fact_inv[b+b]
remove %= MOD

dp = np.zeros(D+D+1,np.int64)
for A in C_to_A[::-1]:
    dp[1:] += dp[:-1].copy()
    np.add.at(dp,A,1)

x = (dp * dp[::-1] % MOD).sum() % MOD
x -= remove
if x&1:
    x += MOD
x //= 2
x %= MOD

print(x)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 + 7

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

D = 2000

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

fact,fact_inv = make_fact(10 ** 4,MOD)
fact = fact.tolist()
fact_inv = fact_inv.tolist()

C_to_A = [[] for _ in range(D+D+1)]
remove = 0
for a,b in AB:
    c = a+b
    C_to_A[c].append(D-a)
    remove += fact[c+c] * fact_inv[a+a] * fact_inv[b+b]
remove %= MOD

dp = np.zeros(D+D+1,np.int64)
for A in C_to_A[::-1]:
    dp[1:] += dp[:-1]
    np.add.at(dp,A,1)

x = (dp * dp[::-1] % MOD).sum() % MOD
x -= remove
if x&1:
    x += MOD
x //= 2
x %= MOD

print(x)

Submission status: Wrong Answer

Solution code:
import math

def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
L = list(list(map(int, input().split())) for i in range(N))

cnt = 0
roop = 0

for i in range(N):
  for j in range(i+1, N):
    n = L[i][0] + L[i][1] + L[j][0] + L[j][1]
    r = L[i][0] + L[j][0]
    cnt += combinations_count(n, r)
    roop += 1
    if roop == 100:
      cnt //= 1000000007
      roop = 0

print(cnt)

Submission status: Wrong Answer

Solution code:
def proc(n):
    res = 1
    for i in range(1,n+1):
        res *= i
    return res

def co(a, b):
    res = proc(a) // proc(a-b) // proc(b)
    return res

n = int(input())

a = [0 for i in range(n)]
b = [0 for i in range(n)]

for ni in range(n):
    a[ni], b[ni] = (int(i) for i in input().split(" "))

res = 0
for i in range(n):
    for j in range(i+1,n):
        res += co(a[i]+a[j]+b[i]+b[j], b[i]+b[j])
        
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())

arr = [map(int,raw_input().split()) for i in range(n)]

count = 0
for i in range(n-1):
	for j in range(i+1,n):
			s = sum(arr[i]) + sum(arr[j])
			comb = s*(s-1)/2
			count += comb

print count%(1000000000+7)

Submission status: Wrong Answer

Solution code:
n = int(input())

arr = [map(int,raw_input().split()) for i in range(n)]

count = 0
for i in range(n-1):
	for j in range(i+1,n):
			s = sum(arr[i]) + sum(arr[j])
			comb = s*(s-1)/2
			count += comb

print count

Submission status: Wrong Answer

Solution code:
n = int(input())

arr = [[map(int,raw_input().split())] for i in range(n)]

count = 0
for i in range(n):
	for j in range(i+1,n):
		if i != j :
			s = sum(arr[i][0]) + sum(arr[j][0])
			comb = s*(s-1)/2
			count += comb

print count

Submission status: Wrong Answer

Solution code:
import math

#--- define function ___#
def counter(x, y):
    return math.factorial(x + y) // (math.factorial(x) * math.factorial(y))
#--- main ___#
N = int(input())
st = []
for i in range(N):
    a, b = input().split()
    st.append([int(a), int(b)])

count = 0
for i in range(N):
    for j in range(i + 1,N):
        l = [a + b for (a, b) in zip(st[i], st[j])]

        ans = counter(l[0], l[1])
        count += ans

print(count)

Submission status: Wrong Answer

Solution code:
ans=0
N=int(input())
kushi=[]
for s in range(N):
	kushi.append(input())
for s in range(N):
	kushi1="".join(kushi[s]).rstrip("\n").split(" ")
	for j in range(N-s):

		if j==0:	continue
		kushi2="".join(kushi[s+j]).rstrip("\n").split(" ")
		n=int(kushi1[0])+int(kushi2[0])+int(kushi1[1])+int(kushi2[1])
		k=int(kushi1[1])+int(kushi2[1])
		nn=n
		kk=k
		for m in range(k-1):
			nn=nn*(n-1)
			kk=kk*(k-1)
			n-=1
			k-=1
		ans+=nn/kk
		print(int(ans))

Submission status: Wrong Answer

Solution code:
ans=0
N=int(input())
kushi=[]
for s in range(N):
	kushi.append(input())
for s in range(N):
	kushi1="".join(kushi[s]).rstrip("\n").split(" ")
	for j in range(N-s):

		if j==0:	continue
		kushi2="".join(kushi[s+j]).rstrip("\n").split(" ")
		n=int(kushi1[0])+int(kushi2[0])+int(kushi1[1])+int(kushi2[1])
		k=int(kushi1[1])+int(kushi2[1])
		for m in range(k-1):
			n=n*(n-1)
			k=k*(k-1)
		ans+=n/k
		print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2]%p)%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(MAX+1):
		for i in xrange(MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup) / 2 + p) % p
solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2]%p)%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup) / 2 + p) % p
solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2]%p)%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+B_MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup) / 2 + p) % p
solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2]%p)%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+B_MAX+1):
			dp[j+1][i] += dp[j][i]
			dp[j][i+1] += dp[j][i]
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup) / 2 + p) % p
solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def solve():
	Base = 10
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2]%p)%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+B_MAX+1):
			dp[j+1][i] += dp[j][i]
			dp[j][i+1] += dp[j][i]
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup) / 2 + p) % p
solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def solve():
	Base = 2000
	p = 10**9+7
	F = [1]; Finv = [0]*(Base*4+1)
	for i in xrange(Base*4): F.append(F[i]*(i+1)%p)
	Finv[Base*4] = pow(F[Base*4],p-2,p)
	for i in xrange(Base*4,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(Base*2+2) for i in xrange(Base*2+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2])%p
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] =(dp[j+1][i]+dp[j][i])%p
			dp[j][i+1] =(dp[j][i+1]+dp[j][i])%p
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print (ans - dup) / 2 % p
solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def solve():
	Base = 2000
	p = 10**9+7
	F = [1]; Finv = [0]*(Base*4+1)
	for i in xrange(Base*4): F.append(F[i]*(i+1))
	Finv[Base*4] = pow(F[Base*4],p-2,p)
	for i in xrange(Base*4,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(Base*2+2) for i in xrange(Base*2+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2])%p
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] += dp[j][i]
			dp[j][i+1] += dp[j][i]
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print (ans - dup) / 2 % p
solve()

Submission status: Wrong Answer

Solution code:
def combi(p,q):
    m=10**9+7
    bunsi=1
    bunbo=1
    for i in range(q):
        bunsi *= (p-i)%m
        bunbo *= (q-i)%m
    bunsi = bunsi%m
    bunbo = bunbo%m
    return bunsi//bunbo % m

ans=0
n=int(input())
k=[]
for i in range(n):
    a,b=map(int,input().split())
    k.append([a,b])

for i in range(n-1):
    for j in range(i+1,n):
        p=k[i][0]+k[i][1]+k[j][0]+k[j][1]
        q=k[i][0]+k[j][0]
        ans += combi(p,q)


ans = ans % (10**9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
L = []
for i in xrange(N):
    l = raw_input()
    L.append(map(int, l.split(" ")))
result = 0
for j in xrange(N):
    M = range(N)
    del M[0:j + 1]
    for k in M:
        niku = (L[j][0] + L[j][1])
        yasai = (L[k][0] + L[k][1])
        niku_tmp = niku
        food = niku + yasai
        p = 1
        q = 1
        for o in xrange(niku):
            p *= food
            q *= niku
            food -= 1
            niku_tmp -= 1
        r = (p % (10**9 + 7)) / (q % (10**9 + 7))
        result += r
print(result * 2) % (10**9 + 7)

Submission status: Wrong Answer

Solution code:
import scipy.misc as scm
def combi(p,q):
    return scm.comb(p,q,1)


ans=0

n=int(input())
k=[]
for i in range(n):
    a,b=map(int,input().split())
    k.append([a,b])

for i in range(n-1):
    for j in range(1,n):
        p=k[i][0]+k[i][1]+k[j][0]+k[j][1]
        q=k[i][0]+k[j][0]
        ans += combi(p,q) % (10**9+7)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
L = []
for x in range(N):
    L.append(list(map(int,input().split())))
val = 0
for i in range(len(L)-1):
    for j in range(i+1,len(L)):
        vvv = (L[i][0] + L[j][0] + L[i][1] + L[j][1])
        val = val + int(((vvv * (vvv-1))/2))
print(val)

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
L = []
for i in xrange(N):
    l = raw_input()
    L.append(map(int, l.split(" ")))
result = 0
for j in xrange(N):
    M = range(N)
    del M[0:j + 1]
    for k in M:
        niku = (L[j][0] + L[j][1])
        yasai = (L[k][0] + L[k][1])
        niku_tmp = niku
        food = niku + yasai
        p = 1
        q = 1
        for o in xrange(niku):
            p *= food
            q *= niku
            food -= 1
            niku_tmp -= 1
        r = (p % (10**9 + 7)) / (q % (10**9 + 7))
        result += r
print(result * 2) % (10**9 + 7)

Submission status: Wrong Answer

Solution code:
import math

set_num = int(raw_input())
bbqsets = []
_append = bbqsets.append
for _ in xrange(set_num):
    _append([ int(x) for x in raw_input().split() ])

maxnum = math.pow(10, 9) + 7

cache = {}
def get_combinations(meats, veges):
    nums = sorted([meats, veges])
    key = '{}:{}'.format(nums[0], nums[1])
    if key in cache:
        return cache[key]
    allnum = meats + veges
    greater = nums[1]
    result = 1.0
    for n in xrange(1, nums[0] + 1):
        t = greater + n
        result *= float(t) / n
    # print key, result
    result = round(result)
    cache[key] = result
    return result

total = 0
for x in xrange(set_num):
    setA = bbqsets[x]
    for y in xrange(x + 1, set_num):
        setB = bbqsets[y]
        meats = setA[0] + setB[0]
        veges = setA[1] + setB[1]
        # print meats, veges
        combinations = get_combinations(meats, veges)
        total += combinations
        if total > maxnum:
            total = total % maxnum
print total

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from itertools import accumulate


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


n = int(sys.stdin.buffer.readline())
mp = map(int, sys.stdin.buffer.read().split())
ab = list(zip(mp, mp))
atob = defaultdict(list)
max_a, max_b = 0, 0
for a, b in ab:
    atob[a].append(b)
    max_a = max(max_a, a)
    max_b = max(max_b, b)

MOD = 10 ** 9 + 7

dp = [0] * (max_b * 2 + 1)
ans = 0
for i in range(-max_a, max_a + 1):
    if i < 0 and -i in atob:
        for j in atob[-i]:
            dp[-j + max_b] += 1
    dp = [x % MOD for x in accumulate(dp)]
    if i > 0 and i in atob:
        for j in atob[i]:
            ans = (ans + dp[j + max_b]) % MOD

facts, invs = prepare(2 * (max_a + max_b), MOD)
ans = int(ans)
for a, b in ab:
    ans = (ans - facts[2 * (a + b)] * invs[2 * a] * invs[2 * b]) % MOD

print(ans * invs[2] % MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
mod = int(1e+9 + 7)

def extgcd(a, b):
  x, y, u, v, k, l = 1, 0, 0, 1, a, b
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x, y

def inved(x):
  a, b = extgcd(x, mod)
  return a % mod

frac = [1]
for i in range(8000):
  frac.append((frac[i]*(i+1))%mod)
invf = []
for i in range(8001):
  invf.append(inved(frac[i]))

A = [list(map(int, input().split())) for i in range(N)]
S = 0
for i in range(N):
  for j in range(i):
    F = frac[A[i][0] + A[j][0] + A[i][1] + A[j][1]] * invf[A[i][0] + A[j][0]]
    F %= mod
    F *= invf[A[i][1] + A[j][1]]
    F %= mod
    S += F
    S %= mod
print(S)

Submission status: Time Limit Exceeded

Solution code:
U = 10**6
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
  fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U],MOD-2,MOD)
 
for i in range(U,0,-1):
  fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def comb(n,k):
  if k < 0 or k > n:
    return 0
  z = fact[n]
  z *= fact_inv[k]
  z %= MOD
  z *= fact_inv[n-k]
  z %= MOD
  return z

n = int(input())
ab = [ list(map(int, input().split())) for _ in range(n) ]
ans = 0
for i in range(n-1):
  for j in range(i+1, n):
    ai, bi = ab[i]
    aj, bj = ab[j]
    ans += comb(ai+bi+aj+bj, ai+aj)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def proc(n):
    res = 1
    for i in range(1,n+1):
        res *= i
    return res

def co(a, b):
    res = proc(a) // proc(a-b) // proc(b)
    return res

n = int(input())

a = [0 for i in range(n)]
b = [0 for i in range(n)]

for ni in range(n):
    a[ni], b[ni] = (int(i) for i in input().split(" "))

res = 0
for i in range(n):
    for j in range(i+1,n):
        res += co(a[i]+a[j]+b[i]+b[j], b[i]+b[j])
        
print(res % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
ans=0
N=int(input())
kushi=[]
def nCk(n,k):
	N,K=n-1,k-1
	tempN=n-1
	tempK=k-1
	for s in range(k-2):
		N=N*(tempN-1)
		K=K*(tempK-1)
		tempN-=1
		tempK-=1
	first=N//K
	N,K=n-1,k
	tempN=n-1
	for s in range(k-1):
		N=N*(tempN-1)
		K=K*(k-1)
		tempN-=1
		k-=1
	second=N//K
	return int(first+second)
for s in range(N):
	kushi.append(input())
for s in range(N):
	kushi1="".join(kushi[s]).rstrip("\n").split(" ")
	for j in range(N-s):

		if j==0:	continue
		kushi2="".join(kushi[s+j]).rstrip("\n").split(" ")

		n=int(kushi1[0])+int(kushi2[0])+int(kushi1[1])+int(kushi2[1])
		k=int(kushi1[1])+int(kushi2[1])
		nn=n
		kk=k
		ans+=nCk(nn,kk)
m=1000000007
print(int(ans)%m)

Submission status: Time Limit Exceeded

Solution code:
ans=0
N=int(input())
kushi=[]

for s in range(N):
	kushi.append(input())
for s in range(N):
	kushi1="".join(kushi[s]).rstrip("\n").split(" ")
	for j in range(N-s):

		if j==0:	continue
		kushi2="".join(kushi[s+j]).rstrip("\n").split(" ")

		n=int(kushi1[0])+int(kushi2[0])+int(kushi1[1])+int(kushi2[1])
		k=int(kushi1[1])+int(kushi2[1])
		nn=n
		kk=k
		for m in range(k-1):
			nn=nn*(n-1)
			kk=kk*(k-1)
			n-=1
			k-=1
		ans+=nn//kk
m=1000000007
print(int(ans)%m)

Submission status: Time Limit Exceeded

Solution code:
ans=0
N=int(input())
kushi=[]

for s in range(N):
	kushi.append(input())
for s in range(N):
	kushi1="".join(kushi[s]).rstrip("\n").split(" ")
	for j in range(N-s):

		if j==0:	continue
		kushi2="".join(kushi[s+j]).rstrip("\n").split(" ")
		n=int(kushi1[0])+int(kushi2[0])+int(kushi1[1])+int(kushi2[1])
		k=int(kushi1[1])+int(kushi2[1])
		nn=n
		kk=k
		for m in range(k-1):
			nn=nn*(n-1)
			kk=kk*(k-1)
			n-=1
			k-=1
		ans+=nn/kk
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# Solution to:
# http://agc001.contest.atcoder.jp/tasks/agc001_e

import numpy as np
from scipy import signal

N = int(raw_input())
A = []
B = []
MAX_SIZE = 2000
MOD = 10**9+7

# Preompute choose table
# CT = [[1], [1, 1]]
# for a in xrange(2, MAX_SIZE*4+2):
#     CT.append([1])
#     for b in xrange(1, a):
#         CT[a].append(CT[a-1][b-1] + CT[a-1][b])
#     CT[a].append(1)

# print "Precomputation done!"

# Precompute factorials
fact = [1]
fact_inv = [1]

for x in xrange(1, MAX_SIZE*2+5):
    fact.append((fact[x-1] * x) % MOD)
    fact_inv.append(pow(fact[x], (MOD-2), MOD))
    # print fact, fact_inv
    # assert (fact[-1] * fact_inv[-1]) % MOD == 1, 'GG'

mat = np.zeros([MAX_SIZE+1, MAX_SIZE+1])
for n in xrange(N):
    a, b = map(int, raw_input().split())
    A.append(a)
    B.append(b)

    mat[a, b] += 1

mixed = signal.fftconvolve(mat, mat)

for n in xrange(N):
    mixed[2*A[n], 2*B[n]] -= 1

mixed /= 2
mixed = np.rint(mixed)

# print mixed[0:5, 0:5]

tsum = 0
for t in xrange(MAX_SIZE*2+2):
    for a in xrange(t+1):
        b = t-a
        if a > MAX_SIZE+1: continue
        if b > MAX_SIZE+1: continue
        # print a,b
        plus = (fact[t] * fact_inv[a]) % MOD
        plus = (plus * fact_inv[b]) % MOD
        # plus = (plus * (t+1)) % MOD
        plus = (plus * int(mixed[a][b])) % MOD
        # if plus > 0: print a,b,plus
        tsum = (tsum + plus) % MOD

print tsum

Submission status: Time Limit Exceeded

Solution code:
import math

set_num = int(raw_input())
bbqsets = []
_append = bbqsets.append
for _ in xrange(set_num):
    _append([ int(x) for x in raw_input().split() ])

maxnum = int(math.pow(10, 9) + 7)

fact = [0] * 8001
rev = [0] * 8001
for i in xrange(0, 8001):
    if i == 0:
        fact[0] = 1
        rev[0] = 1
        continue
    fact[i] = fact[i-1] * i
    rev[i] = pow(fact[i], maxnum - 2, maxnum)

cache = {}
total = 0
for x in xrange(set_num):
    setA = bbqsets[x]
    for y in xrange(x + 1, set_num):
        setB = bbqsets[y]
        nums = tuple(sorted([setA[0] + setB[0], setA[1] + setB[1]]))
        cmb = 0
        if nums in cache:
            cmb = cache[nums]
        else:
            cmb = fact[nums[0] + nums[1]] * rev[nums[0]] * rev[nums[1]]
            cache[nums] = cmb
        # print meats, veges
        total = (total + cmb) % maxnum
print total

Submission status: Time Limit Exceeded

Solution code:
import math

set_num = int(raw_input())
bbqsets = []
_append = bbqsets.append
for _ in xrange(set_num):
    _append([ int(x) for x in raw_input().split() ])

maxnum = int(math.pow(10, 9) + 7)

fact = [0] * 4001
rev = [0] * 4001
for i in xrange(0, 4001):
    if i == 0:
        fact[0] = 1
        rev[0] = 1
        continue
    fact[i] = fact[i-1] * i
    rev[i] = pow(fact[i], maxnum - 2, maxnum)

cache = {}
total = 0
for x in xrange(set_num):
    setA = bbqsets[x]
    for y in xrange(x + 1, set_num):
        setB = bbqsets[y]
        nums = tuple(sorted([setA[0] + setB[0], setA[1] + setB[1]]))
        cmb = 0
        if nums in cache:
            cmb = cache[nums]
        else:
            cmb = fact[nums[0] + nums[1]] * rev[nums[0]] * rev[nums[1]]
            cache[nums] = cmb
        # print meats, veges
        total = (total + cmb) % maxnum
print total

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX*2+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(A,B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (A,B),v in goals.iteritems():
		ans = (ans+(dp[Base+B][Base+A]-F[A*2+B*2]*Finv[A*2]*Finv[B*2]%p)*v) % p
	print (ans + p)*pow(2,p-2,p) % p
solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX*2+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2])%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print (ans - dup + p)*pow(2,p-2,p) % p
solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX*2+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX*2] = pow(F[MAX*2],p-2,p)
	for i in xrange(MAX*2,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2]%p)%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup)*pow(2,p-2,p) + p) % p
solve()