Given two walls A, B with M, N hooks respectively. You are given K ropes. By using one rope you can connect one hook on wall A with another hook on wall B. One hook can connect with only one rope. Find the number of different ways you can use all the K ropes.
Two ways that use the exact same set of hooks from wall A and wall B are considered to be same. 
For Example, 
A1    A2    A3      is same as     A1   A2   A3     and can be ignored.
 |                |                                 |              |      
B1             B2                              B2           B1
Because both knots are using same set of wall A hooks (A1, A3) and same set of wall B hooks (B1,B2)
Note: Answer can be large, return the answer modulo 10^{9}+7. 
Example 1:
Input:
M = 3, N = 2, K = 2
Output: 3
Explanation: 
hooks on Wall A are A1, A2, A3.
hooks on wall B are B1, B2. 
Different Possible Knots are
K1 = (A1-B1, A2-B2), K2 = (A1-B1, A3-B2), 
K3 = (A2-B1, A3-B2)  
Each of these use different set of hooks from wall A. 
Example 2:
Input:
M = 2, N = 2, K = 2
Output: 1
Explanation: 
A1   A2 
|    | 
B1   B2
There is only one way to select 2 hooks 
from wall A and 2 from wall B. 
Your Task:
You do not need to read input or print anything. Your task is to complete the function knots() which takes M, N and K as input parameters and returns the number of possible knots. Return the answer modulo 10^{9}+7.
Expected Time Complexity: O(max(N2, M2))
Expected Auxiliary Space: O(max(N2, M2))
Constraints:
1 ≤ N, M, K ≤ 1000
1 ≤ K ≤ min(N, M)

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Starter code: #User function Template for python3



class Solution:

    def knots(self, M, N, K):

        # code here

Solutions:
class Solution:

	def knots(self, M, N, K):

		def s(a, b):
			i = 1
			j = a
			k = b
			while k > 0:
				k -= 1
				i = i * j
				j -= 1
			p = 1
			for j in range(1, b + 1):
				p = p * j
			return i // p
		ans = s(M, K) * s(N, K)
		return ans % 1000000007


MOD = 10 ** 9 + 7
fact_memo = [1, 1, 2]
inv_fact_memo = [1, 1, (MOD + 1) // 2]

def fact_mod(n):
	m = len(fact_memo)
	while n >= m:
		fact_memo.append(fact_memo[-1] * m % MOD)
		m += 1
	return fact_memo[n]

def inv_fact_mod(n):
	m = len(inv_fact_memo)
	while n >= m:
		inv_fact_memo.append(pow(fact_mod(m), MOD - 2, MOD))
		m += 1
	return inv_fact_memo[n]

def comb_mod(n, k):
	if n < 0 or k < 0 or k > n:
		return 0
	return fact_mod(n) * inv_fact_mod(k) * inv_fact_mod(n - k) % MOD

class Solution:

	def knots(self, M, N, K):
		return comb_mod(M, K) * comb_mod(N, K) % MOD


class Solution:

	def comb(self, n, k):
		res = 1
		fact = 1
		num = 1
		while n > k:
			res = res * n
			n -= 1
			fact = fact * num
			num += 1
		ans = res // fact
		return ans

	def knots(self, M, N, K):
		return self.comb(M, K) * self.comb(N, K) % 1000000007


class Solution:

	def knots(self, M, N, K):
		self.M = M
		self.N = N
		self.K = K

		def fac(n):
			if n == 0:
				return 1
			if n == 1:
				return 1
			if n == 2:
				return 2
			return n * fac(n - 1)
		return fac(self.M) // (fac(self.K) * fac(self.M - self.K)) * (fac(self.N) // (fac(self.K) * fac(self.N - self.K))) % (10 ** 9 + 7)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(M, N, K) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.knots(M, N, K))


class Solution:

	def knots(self, M, N, K):

		def s(a, b):
			i = 1
			j = a
			k = b
			while k > 0:
				k -= 1
				i = i * j
				j -= 1
			p = 1
			for j in range(1, b + 1):
				p = p * j
			return i // p
		ans = s(M, K) * s(N, K)
		return ans % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(M, N, K) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.knots(M, N, K))


from math import factorial as f

class Solution:

	def knots(self, M, N, K):
		return f(M) * f(N) // (f(K) ** 2 * f(M - K) * f(N - K)) % (10 ** 9 + 7)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(M, N, K) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.knots(M, N, K))