Sherry likes matrices a lot, but her favorite ones are humble matrices. An $N\times M$ matrix (we'll call it $\mbox{A}$) is humble if:

It contains all the elements in range $[1,N\times M]$ exactly once.
For any $2$ elements $(i_1,j_1)$ and $(i_2,j_2)$ in matrix $\mbox{A}$:

If $i_{1}+j_{1}<i_{2}+j_{2}$ , then $A_{i_1,j_1}<A_{i_2,j_2}$ should hold. 

Given $N$ and $\mbox{M}$, find and print the total number of possible humble matrices; as this number can be quite large, print your answer modulo $10^9+7$.

Input Format

Two space-separated integers, $N$ and $\mbox{M}$, respectively.

Constraints

$1\leq N,M\leq10^{6}$

Scoring

$1\leq N,M\leq10^3$ for $30\%$ of the test data.  
$1\leq N,M\leq10^{6}$ for $100\%$ of the test data.

Output Format

Print the total number of humble matrices possible, modulo $10^9+7$.

Sample Input 0

2 2

Sample Output 0

2

Sample Input 1

3 2

Sample Output 1

4

Explanation

There are $2$ possible $2\times2$ humble matrices:

[ 1, 2 ] 
[ 3, 4 ]

[ 1, 3 ] 
[ 2, 4 ]

Thus, we print the result of $2\%(10^9+7)$, which is $2$.

Difficulty: MEDIUM
Tags: Combinatorics

Starter code:

Solutions:
M = 10 ** 9 + 7

def main():
	(n, m) = map(int, input().split())
	result = solve(n, m)
	result_mod = result % M
	print(result_mod)

def solve(n, m):
	if n > m:
		(n, m) = (m, n)
	product = 1
	f = 1
	for i in range(1, n):
		f *= i
		f = f % M
		product *= f * f
		product = product % M
	f = f * n % M
	for i in range(m - n + 1):
		product *= f
		product = product % M
	return product
main()


mod = 1000000007
f = [1]
for i in range(1, 1000001):
	f.append(f[-1] * i % mod)
(m, n) = map(int, input().split())
mn = min(m, n)
mx = max(m, n)
r = 1
for i in range(mx - mn + 1):
	r = r * f[mn] % mod
for i in range(1, mn):
	r = r * f[i] % mod
	r = r * f[i] % mod
print(r)


def f(M, N):
	a = min(M, N)
	b = abs(M - N) + 1
	product = 1
	factorial = 1
	for i in range(1, a):
		factorial *= i
		factorial %= 10 ** 9 + 7
		product *= factorial
		product %= 10 ** 9 + 7
	product = pow(product, 2, 10 ** 9 + 7)
	factorial *= a
	product *= pow(factorial, b, 10 ** 9 + 7)
	return product % (10 ** 9 + 7)
(M, N) = map(int, input().split())
print(f(M, N))


(n, m) = [int(i) for i in input().strip().split()]

def fact_gen(n):
	f = 1
	for i in range(1, n):
		yield f
		f *= i
		f %= 10 ** 9 + 7
fact = [i for i in fact_gen(min(n, m) + 2)]
answer = 1
j = 1
for i in range(1, n + m):
	answer *= fact[j]
	answer %= 10 ** 9 + 7
	if i < min(n, m):
		j += 1
	elif i >= max(n, m):
		j -= 1
print(answer)


import math
(n, m) = map(int, input().split())
(n, m) = (min(n, m), max(n, m))
total = 1
fact = 1
for i in range(1, n):
	fact *= i
	fact %= 10 ** 9 + 7
	total *= fact
	total %= 10 ** 9 + 7
	total *= fact
	total %= 10 ** 9 + 7
fact *= n
fact %= 10 ** 9 + 7
for i in range(m - n + 1):
	total *= fact
	total %= 10 ** 9 + 7
print(total)


b = 1000000007
facts = {0: 1, 1: 1}
for i in range(2, 2 * 10 ** 6 + 1):
	facts[i] = i * facts[i - 1] % b
(N, M) = list(map(int, input().strip().split()))
counts = 1
if N == M == 1:
	print(1)
elif N == 1 or M == 1:
	print(1)
else:
	if (N + M - 1) % 2 == 0:
		for i in range((N + M - 1) // 2):
			j = min(i + 1, min(N, M))
			counts = counts % b * (facts[j] % b) % b
			counts = counts % b * (facts[j] % b) % b
	else:
		for i in range((N + M - 1) // 2):
			j = min(i + 1, min(N, M))
			counts = counts % b * (facts[j] % b) % b
			counts = counts % b * (facts[j] % b) % b
		if N == M:
			counts = counts % b * (facts[j + 1] % b) % b
		else:
			counts = counts % b * (facts[j] % b) % b
	print(counts)


modulus = 10 ** 9 + 7
Fact = {0: 1}

def factorial(n):
	if n not in Fact:
		Fact[n] = n * factorial(n - 1) % modulus
	return Fact[n]
(n, m) = [int(i) for i in input().strip().split(' ')]
a = max(n, m)
b = min(n, m)
product = 1
for i in range(a + b - 1):
	product *= factorial(min(i + 1, a + b - 1 - i, b))
	product %= modulus
print(product)


def exp(n, pw, mod):
	res = 1
	for i in range(pw):
		res = res * n % mod
	return res

def mul(facts, mod):
	res = 1
	for i in facts:
		res = res * i % mod
	return res
P = 10 ** 9 + 7
factors = [1]
for i in range(1, 10 ** 6 + 1):
	factors.append(factors[-1] * i % P)
(N, M) = (int(j) for j in input().split())
(N, M) = (max(N, M), min(N, M))
s = exp(mul(factors[1:M], P), 2, P) * exp(factors[M], N - M + 1, P) % P
print(s)


(n, m) = map(int, input().split())
if m > n:
	(n, m) = (m, n)
mod = 10 ** 9 + 7
facs = [1] * (n + 1)
for i in range(1, n + 1):
	facs[i] = facs[i - 1] * i % mod
result = 1
for i in range(1, m):
	result = result * facs[i] * facs[i] % mod
for i in range(1, n - m + 2):
	result = result * facs[m] % mod
print(result)


inf = float('inf')
read_ints = lambda : list(map(int, input().split()))

def solve(N, M):
	(N, M) = (min(N, M), max(N, M))
	MOD = 1000000007
	F = [1] * N
	for i in range(1, N):
		F[i] = F[i - 1] * (i + 1) % MOD
	upper = list(range(N - 1))
	mid = [N - 1] * (M - N + 1)
	lower = list(upper[::-1])
	ans = 1
	for i in upper + mid + lower:
		ans = ans * F[i] % MOD
	return ans
(N, M) = read_ints()
print(solve(N, M))


import math

class ModularInteger:

	def __init__(self, value, N=1000000007):
		self.N = N
		self.value = value % N

	def __add__(self, other):
		return ModularInteger(self.value + other.value)

	def __sub__(self, other):
		assert self.value >= other.value
		return ModularInteger(self.value - other.value)

	def __mul__(self, other):
		return ModularInteger(self.value * other.value)

	def __str__(self):
		return str(self.value)
factorial_memo = [ModularInteger(1)]

def factorial(n):
	if n < len(factorial_memo):
		return factorial_memo[n]
	for i in range(len(factorial_memo), n + 1):
		factorial_memo.append(ModularInteger(i) * factorial_memo[i - 1])
	return factorial_memo[n]

def num_corners(rows, cols):
	n = ModularInteger(1)
	for diag_size in range(1, rows):
		n *= factorial(diag_size)
	return n

def my_pow(base, exponent):
	if exponent == 0:
		return 1
	res = ModularInteger(1)
	for i in range(exponent):
		res *= base
	return res

def num_body(rows, cols):
	num_diags = cols - (rows - 1)
	diag_size = rows
	return my_pow(factorial(diag_size), num_diags)

def solve(n, m):
	rows = min(n, m)
	cols = max(n, m)
	matrices = num_corners(rows, cols)
	matrices *= matrices
	matrices *= num_body(rows, cols)
	return matrices

def main():
	(N, M) = [int(x) for x in input().split()]
	print(solve(N, M))
main()


F = {}

def fac(n):
	if n <= 1:
		return 1
	if n in F:
		return F[n]
	t = n * fac(n - 1) % (10 ** 9 + 7)
	F[n] = t
	return t
(n, m) = (int(a) for a in input().split())
s = 1
N = min(n, m)
M = max(n, m)
for i in range(1, N + M + 1):
	if i <= N:
		c = i
	elif N < i <= M:
		c = N
	else:
		c = N - (i - M)
	s *= fac(c)
	s = s % (10 ** 9 + 7)
print(s)


(n, m) = list(map(int, input().split()))
if n > m:
	(n, m) = (m, n)
res = 1
mod = 10 ** 9 + 7
l = [0] * (10 ** 6 + 1)
l[1] = 1
for i in range(2, n + 1):
	l[i] = l[i - 1] * i % mod
	res *= l[i]
	res %= mod
for i in range(2, n):
	res *= l[i]
	res %= mod
for _ in range(m - n):
	res *= l[n]
	res %= mod
print(res)


MOD = 10 ** 9 + 7
(n, m) = [int(i) for i in input().split()]
fact = [1] * (1 + min(n, m))
for i in range(2, len(fact)):
	fact[i] = i * fact[i - 1] % MOD
p = 1
for i in range(n):
	p = p * fact[min(i + 1, m)] % MOD
for i in range(m - 1):
	p = p * fact[min(n, i + 1)] % MOD
print(p)


(n, m) = [int(x) for x in input().split()]
if n > m:
	(n, m) = (m, n)
mod = 10 ** 9 + 7
facs = [1]
for i in range(1, m + 1):
	facs.append(facs[-1] * i % mod)
res = 1
for i in range(1, n):
	res *= facs[i] * facs[i]
	res %= mod
for i in range(n, m + 1):
	res *= facs[n]
	res %= mod
print(res)


(n, m) = map(int, input().split())
if n > m:
	(n, m) = (m, n)
mod = 10 ** 9 + 7
f = 1
g = 1
for x in range(1, n):
	f = f * x % mod
	g = g * f % mod
F = g ** 2 % mod
res = F * pow(f * n, m - n + 1, mod) % mod
print(res)


mod = 10 ** 9 + 7

def count(n, m):
	k = min(n, m)
	ans = 1
	fact = 1
	for i in range(1, k):
		fact = fact * i % mod
		ans = ans * fact % mod
	ans = ans * ans % mod
	fact = fact * k
	ans = ans * pow(fact, abs(m - n) + 1, mod) % mod
	return ans
(n, m) = [int(x) for x in input().split()]
print(count(n, m))


P = 10 ** 9 + 7
(M, N) = map(int, input().split())
if M < N:
	(M, N) = (N, M)
F = [1] * (M + 1)
for n in range(2, M + 1):
	F[n] = n * F[n - 1] % P
res = 1
for n in range(1, N):
	res = res * pow(F[n], 2, P) % P
res = res * pow(F[N], M - N + 1, P) % P
print(res)


(m, n) = (int(x) for x in input().split())
if m < n:
	(m, n) = (n, m)
rv = 1
p = 1
mod = 1000000007
a = 1
b = m + n - 1
while a <= b:
	if a <= n:
		p = p * a % mod
	rv = rv * p % mod
	if a != b:
		rv = rv * p % mod
	a += 1
	b -= 1
print(rv)


import sys

def f_gen(modulus):
	(f, c) = (1, 1)
	while True:
		yield f
		f = f * c % modulus
		c = (c + 1) % modulus

def solve(n, m, modulus):
	print('n=%d m=%d modulus=%d' % (n, m, modulus), file=sys.stderr)
	(fcache, mn) = ([], min(n, m))
	for (i, f) in enumerate(f_gen(modulus)):
		fcache.append(f)
		if i == mn:
			break
	print('\tfcache=%s' % (fcache[:20],), file=sys.stderr)
	if n < m:
		(n, m) = (m, n)
	total = 1
	k = m - 1
	for i in range(1, k + 1):
		total *= fcache[i]
		total %= modulus
	total *= total
	total %= modulus
	delta = pow(fcache[m], n - k, modulus)
	total *= delta
	total %= modulus
	return total
(n, m) = map(int, input().split())
modulus = pow(10, 9) + 7
print(solve(n, m, modulus))


M = 10 ** 9 + 7
(n, m) = [int(i) for i in input().split()]
fact = [1] * (1 + min(n, m))
for i in range(2, len(fact)):
	fact[i] = i * fact[i - 1] % M
p = 1
for i in range(n):
	p = p * fact[min(i + 1, m)] % M
for i in range(m - 1):
	p = p * fact[min(n, i + 1)] % M
print(p)


mod = 1000000007

def factmod(n, p, m):
	prod = 1
	for i in range(2, n + 1):
		prod = prod * i % m
	return pow(prod, p, m)

def powmod(n, p, m):
	if p == 1:
		return n
	if p == 2:
		return n * n % m
	if p % 2 == 0:
		return powmod(n, p // 2, m) * powmod(n, p // 2, m) % m
	return n * powmod(n, p // 2, m) * powmod(n, p // 2, m) % m

def main():
	(a, b) = map(int, input().split())
	(m, n) = (max(a, b), min(a, b))
	soln = 1
	for i in range(n - 1, 1, -1):
		soln = soln * pow(i, n - i, mod) % mod
	soln = pow(soln, 2, mod)
	soln = soln * factmod(n, m + 1 - n, mod) % mod
	print(soln)
main()


MOD = 10 ** 9 + 7
(n, m) = map(int, input().split())
fact = [1] * (n + m + 1)
ans = 1
for k in range(1, n + m + 1):
	fact[k] = fact[k - 1] * k % MOD
for c in range(0, m):
	k = min(n - 1, c) + 1
	ans = ans * fact[k] % MOD
for r in range(1, n):
	k = min(n - 1 - r, m - 1) + 1
	ans = ans * fact[k] % MOD
print(ans)


M = 10 ** 9 + 7

def main():
	(n, m) = map(int, input().split())
	result = solve(n, m)
	result_mod = result % M
	print(result_mod)

def solve(n, m):
	if n > m:
		(n, m) = (m, n)
	product = 1
	f = 1
	for i in range(1, n):
		f *= i
		f = f % M
		product *= f * f
		product = product % M
	f = f * n % M
	for i in range(m - n + 1):
		product *= f
		product = product % M
	return product
main()


M = 10 ** 9 + 7

def main():
	(n, m) = map(int, input().split())
	result = solve(n, m)
	result_mod = result % M
	print(result_mod)

def solve(n, m):
	if n > m:
		(n, m) = (m, n)
	product = 1
	f = 1
	for i in range(1, n):
		f *= i
		f = f % M
		product *= f * f
		product = product % M
	f = f * n % M
	for i in range(m - n + 1):
		product *= f
		product = product % M
	return product
main()


M = 10 ** 9 + 7

def main():
	(n, m) = map(int, input().split())
	result = solve(n, m)
	result_mod = result % M
	print(result_mod)

def solve(n, m):
	if n > m:
		(n, m) = (m, n)
	product = 1
	f = 1
	for i in range(1, n):
		f *= i
		f = f % M
		product *= f * f
		product = product % M
	f = f * n % M
	for i in range(m - n + 1):
		product *= f
		product = product % M
	return product
main()


M = 10 ** 9 + 7

def main():
	(n, m) = map(int, input().split())
	result = solve(n, m)
	result_mod = result % M
	print(result_mod)

def solve(n, m):
	if n > m:
		(n, m) = (m, n)
	product = 1
	f = 1
	for i in range(1, n):
		f *= i
		f = f % M
		product *= f * f
		product = product % M
	f = f * n % M
	for i in range(m - n + 1):
		product *= f
		product = product % M
	return product
main()


M = 10 ** 9 + 7

def main():
	(n, m) = map(int, input().split())
	result = solve(n, m)
	result_mod = result % M
	print(result_mod)

def solve(n, m):
	if n > m:
		(n, m) = (m, n)
	product = 1
	f = 1
	for i in range(1, n):
		f *= i
		f = f % M
		product *= f * f
		product = product % M
	f = f * n % M
	for i in range(m - n + 1):
		product *= f
		product = product % M
	return product
main()