Alice and the Array solution codechef

Alice and the Array solution codechef – 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\le i \le 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).

Alice and the Array solution codechef

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 \ge 0, Q \gt 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 \ge 0, Q \gt 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.

Alice and the Array solution codechef

  • 1 \leq T \leq 10^3
  • 1 \leq N \leq 2\cdot 10^5
  • The sum of N over all test cases won’t exceed 2\cdot 10^5.

Sample 1:

Input

Output

3
1
2
3
1
250000003
388888893

Alice and the Array solution codechef

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 \gt 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 \lt 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}.

Post navigation

Leave a Reply

Your email address will not be published.