You are given two integers $N$ and ${L}}$. Compute the number of unrooted labelled trees with exactly $N$ nodes and exactly ${L}$ leafs. This number can be huge, so please output it's modulo $10^9+7$.

Input Format

The first line of input consists of two space separated integers $N$ and ${L}$.

Constraints

$1\leq L<N\leq10^{6}$

Output Format

Display an answer to the problem on first line of the output.

Sample Input
5 2
Sample Output

60

Difficulty: HARD
Tags: Combinatorics

Starter code:

Solutions:
import sys
P = 10 ** 9 + 7

def f(n, k):
	if n == 2:
		return 1 if k == 0 else 0

	def C(n, k):
		return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P
	fact = [1]
	for i in range(1, n + 1):
		fact.append(fact[-1] * i % P)
	inv = [0, 1]
	for i in range(2, n + 1):
		inv.append(P - P // i * inv[P % i] % P)
	inv_fact = [1]
	for i in range(1, n + 1):
		inv_fact.append(inv_fact[-1] * inv[i] % P)
	ret = 0
	for used in range(1, k + 1):
		delta = C(k, used) * pow(used, n - 2, P) % P
		if used & 1 == k & 1:
			ret += delta
		else:
			ret -= delta
	return ret % P * C(n, k) % P
(n, l) = map(int, input().split())
k = n - l
print(f(n, k))


mod = 7 + 10 ** 9
N_max = 10 ** 6
fac = [1] * (N_max + 1)
invfac = [1] * (N_max + 1)
for i in range(2, N_max + 1):
	fac[i] = fac[i - 1] * i % mod
invfac[N_max] = pow(fac[N_max], mod - 2, mod)
for i in reversed(range(2, N_max)):
	invfac[i] = invfac[i + 1] * (i + 1) % mod

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * invfac[k] * invfac[n - k] % mod

def stirling_2_kind(n, k):
	ans = 0
	o = 1
	for j in range(k + 1):
		ans = (ans + o * binomial(k, j) * pow(k - j, n, mod)) % mod
		o = -o
	return ans * invfac[k] % mod
import sys

def read_one():
	return sys.stdin.readline().strip()

def read_spaced():
	return sys.stdin.readline().strip().split()

def read_spaced_int():
	return map(int, read_spaced())

def solve(N, L):
	return binomial(N, L) * fac[N - L] * stirling_2_kind(N - 2, N - L) % mod
(N, L) = read_spaced_int()
print(solve(N, L))


import sys
P = 10 ** 9 + 7

def f(n, k):
	if n == 2:
		return 1 if k == 0 else 0

	def C(n, k):
		return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P
	fact = [1]
	for i in range(1, n + 1):
		fact.append(fact[-1] * i % P)
	inv = [0, 1]
	for i in range(2, n + 1):
		inv.append(P - P // i * inv[P % i] % P)
	inv_fact = [1]
	for i in range(1, n + 1):
		inv_fact.append(inv_fact[-1] * inv[i] % P)
	ret = 0
	for used in range(1, k + 1):
		delta = C(k, used) * pow(used, n - 2, P) % P
		if used & 1 == k & 1:
			ret += delta
		else:
			ret -= delta
	return ret % P * C(n, k) % P
(n, l) = map(int, input().split())
k = n - l
print(f(n, k))


mod = 1000000007
factlist = [1]
for i in range(2000001):
	factlist.append(factlist[-1] * (i + 1) % mod)
factinvlist = [0] * len(factlist)
factinvlist[-1] = pow(factlist[-1], mod - 2, mod)
for i in range(len(factlist) - 1, 0, -1):
	factinvlist[i - 1] = factinvlist[i] * i % mod

def choose(n, r):
	if n < r:
		return 0
	else:
		return factlist[n] * factinvlist[r] * factinvlist[n - r] % mod
[n, l] = list(map(int, input().split()))
toprint = 0
for i in range(n + 1 - l):
	toprint += choose(n - l, i) * pow(i, n - 2, mod) * pow(-1, n - l - i)
print(choose(n, l) * toprint % mod)


import sys
P = 10 ** 9 + 7

def f(n, k):
	if n == 2:
		return 1 if k == 0 else 0

	def C(n, k):
		return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P
	fact = [1]
	for i in range(1, n + 1):
		fact.append(fact[-1] * i % P)
	inv = [0, 1]
	for i in range(2, n + 1):
		inv.append(P - P // i * inv[P % i] % P)
	inv_fact = [1]
	for i in range(1, n + 1):
		inv_fact.append(inv_fact[-1] * inv[i] % P)
	ret = 0
	for used in range(1, k + 1):
		delta = C(k, used) * pow(used, n - 2, P) % P
		if used & 1 == k & 1:
			ret += delta
		else:
			ret -= delta
	return ret % P * C(n, k) % P
(n, l) = map(int, input().split())
k = n - l
print(f(n, k))


import sys
P = 10 ** 9 + 7

def f(n, k):
	if n == 2:
		return 1 if k == 0 else 0

	def C(n, k):
		return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P
	fact = [1]
	for i in range(1, n + 1):
		fact.append(fact[-1] * i % P)
	inv = [0, 1]
	for i in range(2, n + 1):
		inv.append(P - P // i * inv[P % i] % P)
	inv_fact = [1]
	for i in range(1, n + 1):
		inv_fact.append(inv_fact[-1] * inv[i] % P)
	ret = 0
	for used in range(1, k + 1):
		delta = C(k, used) * pow(used, n - 2, P) % P
		if used & 1 == k & 1:
			ret += delta
		else:
			ret -= delta
	return ret % P * C(n, k) % P
(n, l) = map(int, input().split())
k = n - l
print(f(n, k))


import sys
P = 10 ** 9 + 7

def f(n, k):
	if n == 2:
		return 1 if k == 0 else 0

	def C(n, k):
		return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P
	fact = [1]
	for i in range(1, n + 1):
		fact.append(fact[-1] * i % P)
	inv = [0, 1]
	for i in range(2, n + 1):
		inv.append(P - P // i * inv[P % i] % P)
	inv_fact = [1]
	for i in range(1, n + 1):
		inv_fact.append(inv_fact[-1] * inv[i] % P)
	ret = 0
	for used in range(1, k + 1):
		delta = C(k, used) * pow(used, n - 2, P) % P
		if used & 1 == k & 1:
			ret += delta
		else:
			ret -= delta
	return ret % P * C(n, k) % P
(n, l) = map(int, input().split())
k = n - l
print(f(n, k))


import sys
P = 10 ** 9 + 7

def f(n, k):
	if n == 2:
		return 1 if k == 0 else 0

	def C(n, k):
		return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P
	fact = [1]
	for i in range(1, n + 1):
		fact.append(fact[-1] * i % P)
	inv = [0, 1]
	for i in range(2, n + 1):
		inv.append(P - P // i * inv[P % i] % P)
	inv_fact = [1]
	for i in range(1, n + 1):
		inv_fact.append(inv_fact[-1] * inv[i] % P)
	ret = 0
	for used in range(1, k + 1):
		delta = C(k, used) * pow(used, n - 2, P) % P
		if used & 1 == k & 1:
			ret += delta
		else:
			ret -= delta
	return ret % P * C(n, k) % P
(n, l) = map(int, input().split())
k = n - l
print(f(n, k))


import sys
P = 10 ** 9 + 7

def f(n, k):
	if n == 2:
		return 1 if k == 0 else 0

	def C(n, k):
		return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P
	fact = [1]
	for i in range(1, n + 1):
		fact.append(fact[-1] * i % P)
	inv = [0, 1]
	for i in range(2, n + 1):
		inv.append(P - P // i * inv[P % i] % P)
	inv_fact = [1]
	for i in range(1, n + 1):
		inv_fact.append(inv_fact[-1] * inv[i] % P)
	ret = 0
	for used in range(1, k + 1):
		delta = C(k, used) * pow(used, n - 2, P) % P
		if used & 1 == k & 1:
			ret += delta
		else:
			ret -= delta
	return ret % P * C(n, k) % P
(n, l) = map(int, input().split())
k = n - l
print(f(n, k))


import sys
P = 10 ** 9 + 7

def f(n, k):
	if n == 2:
		return 1 if k == 0 else 0

	def C(n, k):
		return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P
	fact = [1]
	for i in range(1, n + 1):
		fact.append(fact[-1] * i % P)
	inv = [0, 1]
	for i in range(2, n + 1):
		inv.append(P - P // i * inv[P % i] % P)
	inv_fact = [1]
	for i in range(1, n + 1):
		inv_fact.append(inv_fact[-1] * inv[i] % P)
	ret = 0
	for used in range(1, k + 1):
		delta = C(k, used) * pow(used, n - 2, P) % P
		if used & 1 == k & 1:
			ret += delta
		else:
			ret -= delta
	return ret % P * C(n, k) % P
(n, l) = map(int, input().split())
k = n - l
print(f(n, k))