recovering-grid-revisited

Instead of one grid various square grids of odd length came into existence later after the old grid was recovered. Now researchers came to know that for such grids the sum of all the numbers except the middle element is equal to the middle element of the grid. Now since all numbers are disappeared so you need to find total possible solutions the grid can possess. Remember that each element of the grid solution should possess only non negative numbers 
Input
First line contains t (test cases) ,next t lines contain N and M as input  , N will be odd and is the size of the grid and M is the value of the middle element of the grid 
Output
You have to output count of total solutions that the grid can posses mod 10^9+7.
Scoring
1≤ t,N,M ≤ 10      20pts
1≤ t,N,M ≤ 100    30pts
1≤ t ≤ 10^5 , 1≤ N,M ≤ 10^3  50pts

SAMPLE INPUT
1
3 1

SAMPLE OUTPUT
8

Explanation

The all possible solutions to the grid are insert 1 in 8 distinct positions and fill rest with zeros.

Source: hackerearth | Difficulty: EASY


Solutions:
def fast_expo(a,b,mod):
	result = 1
	while(b>0):
		if b%2==1:
			result*=a
			result%=mod
		a=(a*a)%mod
		b=b/2
	return result
		




def precompute(fact,inv,mod):

	fact[0],fact[1]= 1,1
	for i in range(2,len(fact)):
		fact[i] = (i*fact[i-1])%mod
 
	inv[len(inv)-1] = fast_expo(fact[len(inv)-1],mod-2,mod)
	for i in range(len(inv)-2,-1,-1):
		inv[i] = ((i+1)*inv[i+1])%mod
   
		

fact = [0]*(10**7)
inv  = [0]*(10**7)
mod  = 10**9 + 7

precompute(fact,inv,mod)

T = int(input())
for t in range(T):
	N,M = [int(x) for x in input().split()]
  
	n = M + N*N -2
	r = N*N -2
	if n>=r and n>=0 and r>=0:
		print((((fact[n]*inv[r])%mod)*inv[n-r])%mod)
	else:
		print(0)

	
	





import math
modulo=(10**9)+7
fa=[1]
for i in range(1,2000000):
	fa.append((fa[i-1]*i)%modulo)
def combination(n,r):
	numerator=fa[n]
	denominator=(fa[r]*fa[n-r])%modulo
	den=pow(denominator,modulo-2,modulo)
	return (numerator*den)%modulo
t=eval(input())
for i in range(t):
	s=input().split(' ')
	n=int(s[0])
	m=int(s[1])
	t=m+n*n-2
	answer=combination(t,m)
	if n==1:
		answer=0
	print(answer)