Alice is playing a game with permutations of size N.  

She selects a random *permutation* P of size N and a random index i (1≤ i ≤ N); 
She keeps incrementing the index i until:
- The next element is greater than the current element (P_{(i+1)} > P_{i}), or;
- She reaches the last index (i = N).

Find the [expected] number of indices that Alice will visit throughout the game.

It can be shown that this expected value can be expressed as a fraction \frac{P}{Q}, where P and Q are coprime integers, P ≥ 0, Q > 0 and Q is coprime with 10^{9} + 7. You should compute P \cdot Q^{-1} \% (10^{9} + 7), where Q^{-1} denotes the multiplicative inverse of Q modulo 10^{9}+7.

Note that a *permutation* of size N consists of all integers from 1 to N, where each element is present exactly once.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of single lines of input containing an integer N, the size of permutation.
    
------ Output Format ------ 

For each test case, print in a single line, the expected number of indices that Alice will visit throughout the game.

It can be shown that this expected value can be expressed as a fraction \frac{P}{Q}, where P and Q are coprime integers, P ≥ 0, Q > 0 and Q is coprime with 10^{9} + 7. You should compute P \cdot Q^{-1} \% (10^{9} + 7), where Q^{-1} denotes the multiplicative inverse of Q modulo 10^{9}+7.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 2\cdot 10^{5}$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
1
2
3

----- Sample Output 1 ------ 
1
250000003
388888893

----- explanation 1 ------ 
Test case $1$: There is only one possible way to select a permutation of size $1$ and an index from the permutation $1$. Thus, we choose $P = \{1\}$ and $i = 1$. The number of indices covered after this choice is $1$.

Test case $2$: The possible cases are:
- $P = \{1, 2\}$ and $i = 1$: We cannot increment the index $i=1$ as $P_{2} > P_{1}$. Thus, number of indices covered is $1$.
- $P = \{1, 2\}$ and $i = 2$: We cannot increment the index $i=2$ as it is the last index. Thus, number of indices covered is $1$.
- $P = \{2, 1\}$ and $i = 1$: We can increment the index $i=1$ as $P_{2} < P_{1}$. We reach index $i = 2$. Now we cannot increment the index. Thus, number of indices covered is $2$.
- $P = \{2, 1\}$ and $i = 2$: We cannot increment the index $i=2$ as it is the last index. Thus, number of indices covered is $1$.

Thus, the expected value of number of indices visited is $\frac{3}{4}\cdot 1 + \frac{1}{4}\cdot 2 = \frac{5}{4}$.

Difficulty: VERY_HARD
Tags: Combinatorics

Mathematics

Probability

Starter code:

Solutions:
fact_l = [1]
a_vals = [0]
mod = 10 ** 9 + 7
for t in range(int(input())):
	n = int(input())
	while n + 1 >= len(fact_l):
		fact_l.append(fact_l[len(fact_l) - 1] * len(fact_l) % mod)
		a_vals.append((a_vals[len(a_vals) - 1] * len(a_vals) + 1) % mod)
	P = (a_vals[n + 1] - a_vals[n] - fact_l[n]) % mod
	Q = fact_l[n] * n % mod
	Q = pow(Q, -1, mod)
	print(P * Q % mod)


(a, b) = [[0], [1]]
for i in range(1, 200010):
	a.append((a[i - 1] * i + 1) % 1000000007)
	b.append(b[i - 1] * i % 1000000007)
for _ in range(int(input())):
	n = int(input())
	print(((a[n + 1] - a[n] - b[n]) * pow(b[n] * n, 1000000005, 1000000007) % 1000000007 + 1000000007) % 1000000007)


N = 200001
mod = 1000000007

def inv(x):
	return pow(x, mod - 2, mod)
fac = [0] * (N + 10)
isfac = [0] * (N + 10)
ans = [0] * (N + 10)
last = [0] * (N + 10)

def init():
	fac[0] = 1
	for i in range(1, N + 1):
		fac[i] = fac[i - 1] * i % mod
		isfac[i] = (isfac[i - 1] + inv(fac[i])) % mod
	ans[1] = 1
	last[1] = 1
	for i in range(2, N + 1):
		last[i] = isfac[i]
		ans[i] = (ans[i - 1] * (i - 1) + last[i]) * inv(i) % mod

def work(n):
	return ans[n]
init()
T = int(input())
for _ in range(T):
	print(work(int(input())))


(c, d) = [[0], [1]]
zero = 0
for i in range(1, 200010):
	c.append((c[i - 1] * i + 1 + zero) % 1000000007)
	d.append(d[i - 1] * i % 1000000007)
for _ in range(int(input())):
	n = int(input())
	print(((c[n + 1] - c[n] - d[n]) * pow(d[n] * n, 1000000005, 1000000007) % 1000000007 + 1000000007) % 1000000007)


(xy, qw) = [[0], [1]]
for e in range(1, 200010):
	xy.append((xy[e - 1] * e + 1) % 1000000007)
	qw.append(qw[e - 1] * e % 1000000007)
for _ in range(int(input())):
	jk = int(input())
	print(((xy[jk + 1] - xy[jk] - qw[jk]) * pow(qw[jk] * jk, 1000000005, 1000000007) % 1000000007 + 1000000007) % 1000000007)


mod = 1000000007
SIZE = 1000000
fact = [1] * SIZE
fact2 = [0] * SIZE

def factorial():
	for i in range(1, SIZE):
		fact[i] = fact[i - 1] * i % mod
		fact2[i] = (i * fact2[i - 1] + 1) % mod

def modInverse(A, M):
	m0 = M
	y = 0
	x = 1
	if M == 1:
		return 0
	while A > 1:
		q = A // M
		t = M
		M = A % M
		A = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
factorial()
t = int(input())
for i in range(t):
	n = int(input())
	inv = modInverse(n * fact[n], 1000000007)
	g = (fact2[n + 1] - fact2[n] - fact[n]) % 1000000007
	if g < 0:
		g += 1000000007
	print(inv * g % 1000000007)


mod = 1000000007
T = int(input())
b = [0, 1]
factorial = [1, 1]
for testNum in range(T):
	n = int(input())
	if n >= len(b):
		for i in range(len(b), n + 1):
			b.append((b[i - 1] * i + 1) % mod)
			factorial.append(factorial[i - 1] * i % mod)
	p = n * b[n] + 1 - factorial[n]
	q = n * factorial[n]
	q = pow(q, -1, mod)
	result = p * q % mod
	print(result)