10272. Reduce to one

 

Consider a list of integers L. Initially, L contains all integers from 1 to n, each exactly once (later, the list may contain multiple copies of some numbers). The order of elements in L does not matter. You need to perform the following operation n – 1 times:

·        Select two elements from the list, denoted by x and y. They may be equal.

·        Remove the selected elements from L.

·        Add the number x + y + x * y to the list.

As a result, the list will contain exactly one number. Find the maximum possible value of this number. Since the answer can be large, print it modulo 109 + 7.

 

Input. The first line contains the number of test cases t. Each of the next t lines contains one integer n (1 ≤ n ≤ 106).

 

Output. For each test case, print one integer – the maximum possible value of the last number in the list, computed modulo 109 + 7.

 

Sample input

Sample ouutput

3

1

2

4

1

5

119

 

 

SOLUTION

mathematics

 

Algorithm analysis

First, transform the expression:

x + y + x * y = y * (x + 1) + (x + 1) – 1 = (x + 1) * (y + 1) – 1

Now, the operation can be seen as multiplying two numbers, each increased by 1, and then subtracting 1.

If we remove the numbers x and y from the list, the following number will be added to the list:

(x + 1) * (y + 1) – 1

Next, remove from the list the numbers (x + 1) * (y + 1) – 1 and z. Then the number added to the list will be

((x + 1) * (y + 1) – 1 + 1) * (z + 1) – 1 =

(x + 1) * (y + 1) * (z + 1) – 1

Following this analogy, we can conclude that if initially

L = {a1, a2, …, an},

then at the end the remaining number will be

(a1 + 1) * (a2 + 1) * … * (an + 1) – 1

Since initially L contains all integers from 1 to n, the final number will be

(1 + 1) * (2 + 1) * … * (n + 1) – 1 = (n + 1)! – 1

The resulting number is uniquely determined and does not depend on the order in which the operations are performed.

 

Algorithm implementation

Declare the constants.

 

#define MOD 1000000007

#define MAX 1000002

 

The input contains multiple test cases. Declare an array p such that p[i] = i!.

 

long long p[MAX];

 

Read the number of test cases tests. Compute the factorials of the numbers and store them in the array: p[i] = i!

 

scanf("%d", &tests);

p[1] = 1;

for (i = 2; i < MAX; i++)

  p[i] = (p[i - 1] * i) % MOD;

 

Process the test cases sequentially.

 

while (tests--)

{

 

For each input value n print the answer – the value (n + 1)! – 1.

 

  scanf("%d", &n);

  printf("%lld\n", p[n + 1] - 1);

}

 

Python implementation

Declare the constants.

 

MOD = 1000000007

MAX = 1000002

 

Compute the factorials of the numbers and store them in the list: p[i] = i!

 

p = [1] * MAX

for i in range(2, MAX):

  p[i] = (p[i - 1] * i) % MOD

 

Read the number of test cases tests.

 

tests = int(input())

 

Process the test cases sequentially.

 

for _ in range(tests):

 

For each input value n print the answer – the value (n + 1)! – 1.

 

  n = int(input())

  print(p[n + 1] - 1)