You are given a set A containing n integers from 1 to n; A = {1,2,3,...n}. 

Let's call P(A) as a set that contains all permutations of A; 

For eg: if A = {1,2}. P(A) = {{1,2},{2,1}}

Can you find the number of elements a ∈ P(A) which satisfies following conditions:

For every 1 <= i <= n, a[i] ≠ i where a[i] is the i^{th} integer in permutation a
There exists a set of k integers {i_{1}, i_{2}, i_{3}, .... i_{k}} such that 
a[i_{j}] = i_{j+1} ∀ j < k and a[i_{k}] = i1 (cyclic)

Input Format 

The first line contains an integer T indicating the number of test-cases.
T lines follow. Each line has two integers n and k separated by a single space.

Constraints 

1 <= T <= 100 

1 <= k <= n <= 10^{6}

Output Format 

Output the remainder of the answer after divided by 1000000007 ie., (10^{9}+7)

Sample Input

4
3 2
4 2
5 3
6 2

Sample Output

0
3
20
105

Hint

10^{9}+7 is a prime number.

Explanation

note : Array's are 1 indexed. 

Lets take a look at N = 3 and K = 2

We will get 2 sets of A that satisfy the first property a[i] ≠ i, they are 

[3,1,2]
[2,3,1]

Now, as K = 2, we can have 6 such elements. 

[1,2], [1,3],[2,3], [2,1], [3,1], [3,2]

Lets consider the first element of P(A) -> [3,1,2] 

[1,2], a[1] ≠ 2
[1,3], a[1] = 3 but a[3] ≠ 1
[2,3], a[2] ≠ 3
[2,1], a[2] = 1 but a[1] ≠ 2
[3,1], a[3] = 1 but a[1] ≠ 3
[3,2], a[3] ≠ 2

Lets consider the second element of P(A) -> [2,3,1]

[1,2], a[1] = 2 but a[2] ≠ 1
[1,3], a[1] ≠ 3
[2,3], a[2] = 3 but a[3] ≠ 3
[2,1], a[2] ≠ 1
[3,1], a[3] = but a[1] ≠ 3
[3,2], a[3] ≠ 2

As none of the elements of a satisfy the properties above, hence 0. 

In the second case, n=4,k=2. Here follows all the permutations of 

A={1,2,3,4} we could find that satisfy the two condition above.

2 1 4 3 # (a[2] = 1, a[1] = 2) or (a[4] = 3, a[3] = 4) is ok.

4 3 2 1 # (a[4] = 1, a[1] = 4) or (a[3] = 2, a[2] = 3) is ok.

3 4 1 2 # (a[3] = 1, a[1] = 3) or (a[4] = 2, a[2] = 4) is ok.

Timelimits
Timelimits for this challenge is given here

Source: hackerrank | Difficulty: MEDIUM
Tags: Combinatorics


Solutions:
modulus = 10 ** 9 + 7
stop = 10 ** 6 + 1

def extended_euclid(a, b):
	(r0, r1) = (a, b)
	(s0, s1) = (1, 0)
	(t0, t1) = (0, 1)
	while r1 != 0:
		(q, r2) = divmod(r0, r1)
		s2 = s0 - q * s1
		t2 = t0 - q * t1
		(r0, s0, t0) = (r1, s1, t1)
		(r1, s1, t1) = (r2, s2, t2)
	return (r0, s0, t0)

def modular_inverse(n, modulus):
	t = extended_euclid(modulus, n)[2]
	if t < 0:
		return t + modulus
	return t
derangements = [1, 0]
factorials = [1, 1]
for j in range(2, stop):
	new_derangements = derangements[-1] * j + (-1) ** j
	derangements.append(new_derangements % modulus)
	new_factorial = factorials[-1] * j
	factorials.append(new_factorial % modulus)

def count_up(n, k):
	if k == 1:
		return 0
	ans = 0
	base_denom = modular_inverse(k, modulus)
	base_num = factorials[n]
	for j in range(1, n // k + 1):
		sign = (-1) ** (j - 1)
		derangement_count = derangements[n - k * j]
		numerator = base_num
		denominator = pow(base_denom, j, modulus)
		denominator *= modular_inverse(factorials[n - k * j], modulus)
		denominator *= modular_inverse(factorials[j], modulus)
		ans += sign * derangement_count * numerator * denominator
		ans = ans % modulus
	return ans
T = int(input())
for j in range(T):
	(n, k) = [int(x) for x in input().split()]
	print(count_up(n, k))


MOD = 1000000007

def inv(x):
	return pow(x, MOD - 2, MOD)
f = [1]
sums = [1]

def init(n):
	sign = -1
	for i in range(1, n + 1):
		f.append(f[-1] * i % MOD)
		sums.append((sums[-1] + sign * inv(f[-1])) % MOD)
		sign = -sign

def D(n):
	return f[n] * sums[n] % MOD

def compute(n, k):
	if k == 1:
		return 0
	result = 0
	sign = 1
	for m in range(1, n // k + 1):
		result = (result + sign * inv(pow(k, m, MOD) * f[m] * f[n - m * k]) * D(n - m * k)) % MOD
		sign = -sign
	return result * f[n] % MOD
nk = [list(map(int, input().split())) for _ in range(int(input()))]
init(max([n for (n, k) in nk]))
for (n, k) in nk:
	print(compute(n, k))


mod = 1000000007
factlist = [1]
derangements = [1]
for i in range(1, 1000001):
	factlist.append(factlist[-1] * i % mod)
	derangements.append((i * derangements[-1] + (-1 if i % 2 else 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
t = int(input())
for _ in range(t):
	[n, k] = list(map(int, input().split()))
	if k == 1:
		print(0)
		continue
	toprint = 0
	currmult = pow(k, mod - 2, mod)
	powmult = -currmult
	for j in range(1, n // k + 1):
		toprint += currmult * factinvlist[n - j * k] * factinvlist[j] * derangements[n - j * k]
		currmult *= powmult
	print(toprint * factlist[n] % mod)


modulus = 10 ** 9 + 7
stop = 10 ** 6 + 1

def extended_euclid(a, b):
	(r0, r1) = (a, b)
	(s0, s1) = (1, 0)
	(t0, t1) = (0, 1)
	while r1 != 0:
		(q, r2) = divmod(r0, r1)
		s2 = s0 - q * s1
		t2 = t0 - q * t1
		(r0, s0, t0) = (r1, s1, t1)
		(r1, s1, t1) = (r2, s2, t2)
	return (r0, s0, t0)

def modular_inverse(n, modulus):
	t = extended_euclid(modulus, n)[2]
	if t < 0:
		return t + modulus
	return t
derangements = [1, 0]
factorials = [1, 1]
for j in range(2, stop):
	new_derangements = derangements[-1] * j + (-1) ** j
	derangements.append(new_derangements % modulus)
	new_factorial = factorials[-1] * j
	factorials.append(new_factorial % modulus)

def count_up(n, k):
	if k == 1:
		return 0
	ans = 0
	base_denom = modular_inverse(k, modulus)
	base_num = factorials[n]
	for j in range(1, n // k + 1):
		sign = (-1) ** (j - 1)
		derangement_count = derangements[n - k * j]
		numerator = base_num
		denominator = pow(base_denom, j, modulus)
		denominator *= modular_inverse(factorials[n - k * j], modulus)
		denominator *= modular_inverse(factorials[j], modulus)
		ans += sign * derangement_count * numerator * denominator
		ans = ans % modulus
	return ans
T = int(input())
for j in range(T):
	(n, k) = [int(x) for x in input().split()]
	print(count_up(n, k))


modulus = 10 ** 9 + 7
stop = 10 ** 6 + 1

def extended_euclid(a, b):
	(r0, r1) = (a, b)
	(s0, s1) = (1, 0)
	(t0, t1) = (0, 1)
	while r1 != 0:
		(q, r2) = divmod(r0, r1)
		s2 = s0 - q * s1
		t2 = t0 - q * t1
		(r0, s0, t0) = (r1, s1, t1)
		(r1, s1, t1) = (r2, s2, t2)
	return (r0, s0, t0)

def modular_inverse(n, modulus):
	t = extended_euclid(modulus, n)[2]
	if t < 0:
		return t + modulus
	return t
derangements = [1, 0]
factorials = [1, 1]
for j in range(2, stop):
	new_derangements = derangements[-1] * j + (-1) ** j
	derangements.append(new_derangements % modulus)
	new_factorial = factorials[-1] * j
	factorials.append(new_factorial % modulus)

def count_up(n, k):
	if k == 1:
		return 0
	ans = 0
	base_denom = modular_inverse(k, modulus)
	base_num = factorials[n]
	for j in range(1, n // k + 1):
		sign = (-1) ** (j - 1)
		derangement_count = derangements[n - k * j]
		numerator = base_num
		denominator = pow(base_denom, j, modulus)
		denominator *= modular_inverse(factorials[n - k * j], modulus)
		denominator *= modular_inverse(factorials[j], modulus)
		ans += sign * derangement_count * numerator * denominator
		ans = ans % modulus
	return ans
T = int(input())
for j in range(T):
	(n, k) = [int(x) for x in input().split()]
	print(count_up(n, k))


modulus = 10 ** 9 + 7
stop = 10 ** 6 + 1

def extended_euclid(a, b):
	(r0, r1) = (a, b)
	(s0, s1) = (1, 0)
	(t0, t1) = (0, 1)
	while r1 != 0:
		(q, r2) = divmod(r0, r1)
		s2 = s0 - q * s1
		t2 = t0 - q * t1
		(r0, s0, t0) = (r1, s1, t1)
		(r1, s1, t1) = (r2, s2, t2)
	return (r0, s0, t0)

def modular_inverse(n, modulus):
	t = extended_euclid(modulus, n)[2]
	if t < 0:
		return t + modulus
	return t
derangements = [1, 0]
factorials = [1, 1]
for j in range(2, stop):
	new_derangements = derangements[-1] * j + (-1) ** j
	derangements.append(new_derangements % modulus)
	new_factorial = factorials[-1] * j
	factorials.append(new_factorial % modulus)

def count_up(n, k):
	if k == 1:
		return 0
	ans = 0
	base_denom = modular_inverse(k, modulus)
	base_num = factorials[n]
	for j in range(1, n // k + 1):
		sign = (-1) ** (j - 1)
		derangement_count = derangements[n - k * j]
		numerator = base_num
		denominator = pow(base_denom, j, modulus)
		denominator *= modular_inverse(factorials[n - k * j], modulus)
		denominator *= modular_inverse(factorials[j], modulus)
		ans += sign * derangement_count * numerator * denominator
		ans = ans % modulus
	return ans
T = int(input())
for j in range(T):
	(n, k) = [int(x) for x in input().split()]
	print(count_up(n, k))


modulus = 10 ** 9 + 7
stop = 10 ** 6 + 1

def extended_euclid(a, b):
	(r0, r1) = (a, b)
	(s0, s1) = (1, 0)
	(t0, t1) = (0, 1)
	while r1 != 0:
		(q, r2) = divmod(r0, r1)
		s2 = s0 - q * s1
		t2 = t0 - q * t1
		(r0, s0, t0) = (r1, s1, t1)
		(r1, s1, t1) = (r2, s2, t2)
	return (r0, s0, t0)

def modular_inverse(n, modulus):
	t = extended_euclid(modulus, n)[2]
	if t < 0:
		return t + modulus
	return t
derangements = [1, 0]
factorials = [1, 1]
for j in range(2, stop):
	new_derangements = derangements[-1] * j + (-1) ** j
	derangements.append(new_derangements % modulus)
	new_factorial = factorials[-1] * j
	factorials.append(new_factorial % modulus)

def count_up(n, k):
	if k == 1:
		return 0
	ans = 0
	base_denom = modular_inverse(k, modulus)
	base_num = factorials[n]
	for j in range(1, n // k + 1):
		sign = (-1) ** (j - 1)
		derangement_count = derangements[n - k * j]
		numerator = base_num
		denominator = pow(base_denom, j, modulus)
		denominator *= modular_inverse(factorials[n - k * j], modulus)
		denominator *= modular_inverse(factorials[j], modulus)
		ans += sign * derangement_count * numerator * denominator
		ans = ans % modulus
	return ans
T = int(input())
for j in range(T):
	(n, k) = [int(x) for x in input().split()]
	print(count_up(n, k))


modulus = 10 ** 9 + 7
stop = 10 ** 6 + 1

def extended_euclid(a, b):
	(r0, r1) = (a, b)
	(s0, s1) = (1, 0)
	(t0, t1) = (0, 1)
	while r1 != 0:
		(q, r2) = divmod(r0, r1)
		s2 = s0 - q * s1
		t2 = t0 - q * t1
		(r0, s0, t0) = (r1, s1, t1)
		(r1, s1, t1) = (r2, s2, t2)
	return (r0, s0, t0)

def modular_inverse(n, modulus):
	t = extended_euclid(modulus, n)[2]
	if t < 0:
		return t + modulus
	return t
derangements = [1, 0]
factorials = [1, 1]
for j in range(2, stop):
	new_derangements = derangements[-1] * j + (-1) ** j
	derangements.append(new_derangements % modulus)
	new_factorial = factorials[-1] * j
	factorials.append(new_factorial % modulus)

def count_up(n, k):
	if k == 1:
		return 0
	ans = 0
	base_denom = modular_inverse(k, modulus)
	base_num = factorials[n]
	for j in range(1, n // k + 1):
		sign = (-1) ** (j - 1)
		derangement_count = derangements[n - k * j]
		numerator = base_num
		denominator = pow(base_denom, j, modulus)
		denominator *= modular_inverse(factorials[n - k * j], modulus)
		denominator *= modular_inverse(factorials[j], modulus)
		ans += sign * derangement_count * numerator * denominator
		ans = ans % modulus
	return ans
T = int(input())
for j in range(T):
	(n, k) = [int(x) for x in input().split()]
	print(count_up(n, k))