little-deepu-vs-little-kuldeep

Little Deepu and Little Kuldeep are the two best warriors in the realm of Westeros. But, their priorities and their loyalties are very much divided. Little Kuldeep fights for the right, just while Little Deepu fights for the wrong reasons, and supports the wrong ones in the kingdom.  Everyone's scared of these two warriors getting into a fight ever. But, in the final match of the tournament for the best warrior in the kingdom, these two warriors will eventually have to face each other. 

But, here's the twist. Since, everyone knows that these two are the best ones, no one wants them to die. So, it's a no-kill contest between them. They CANNOT kill each other. They just have to hit each other, with their best moves.

Both, Little Deepu and Little Kuldeep will get n chances to hit the opponent. But, since Little Deepu fights for the wrong people, he had the power to convince people that he'll be the attacker, and Kuldeep be the defender - that is to say. So, what will happen is the following: Little Kuldeep  CANNOT attack Little Deepu before Little Deepu attacks him. Little Kuldeep can only retaliate to Little Deepu's hits, and NOT hit him before Deepu hits him.

That is to say, let's say both of them have 3 moves. So, a valid hitting combination would be:
1. DDDKKK
2. DKDDKK
And 3 other combinations.

So, ONLY after Deepu hits Kuldeep can hit him back!

So, you being a volunteer in managing the fights, have to figure out the number of valid combinations of the n hits by the both of them.

Input format:
The first line contains the number of test cases.
Every test case contains an integer N.

Output format:
You've to print out the number of valid combinations modulo by 1000000007.

Constraints:
1 ≤ Test Cases < 1001
1 ≤ N ≤ 1000000  

SAMPLE INPUT
2
2
1548

SAMPLE OUTPUT
2
57584392

Source: hackerearth | Difficulty: MEDIUM
Tags: Mathematics


Solutions:
# Binomial coefficient with mod inverse of prime.  Calculate binom (n, r) % p.
MAXN = 2000005
MOD = 1000000007
f = [0] * MAXN
def binom (n, r, p):
	# print binom (10 ** 18, 2545354543534, 9973)
	if n < 0 or r < 0 or n < r: return 0

	# Precalculate factorial.
	if f [0] != 1:  # Factorial already precalculated.
		f [0] = 1
		for i in range (1, MAXN): f [i] = (i * f [i - 1]) % p

	# Calculate modular inverse using Fermat's little theorum.
	def inv (n): return  pow (n, p - 2, p)

	ret = 1
	while n or r:
		# Use Lucas theorum to reduce values into its prime residual.
		n0, r0 = n % p, r % p
		n, r = n / p, r / p
		if n0 < r0: return 0
		# print n0, r0
		ret *= f [n0] * inv (f [r0]) * inv (f [n0 - r0])
		ret %= p

	return ret

T = int (input ())
for t in range (T):
	N = int (input ())
	print((binom (2 * N, N, MOD) * pow (N + 1, MOD - 2, MOD)) % MOD)