# Reduce to One | Codechef solution

Problem:-

You have become good friends with Chef. Right now, Chef is busy in the kitchen, so he asked you to solve a problem for him.

Consider a list of integers $�$. Initially, $�$ contains the integers $1$ through $�$, each of them exactly once (but it may contain multiple copies of some integers later). The order of elements in $�$ is not important. You should perform the following operation $�-1$ times:

• Choose two elements of the list, let's denote them by $�$ and $�$. These two elements may be equal.
• Erase the chosen elements from $�$.
• Append the number $�+�+�\cdot �$ to $�$.

At the end, $�$ contains exactly one integer. Find the maximum possible value of this integer. Since the answer may be large, compute it modulo $1,000,000,007$ ($1{0}^{9}+7$).

### Input

• The first line of the input contains a single integer $�$ denoting the number of test cases. The description of $�$ test cases follows.
• The first and only line of each test case contains a single integer $�$.

### Output

For each test case, print a single line containing one integer ― the maximum possible value of the final number in the list modulo $1{0}^{9}+7$.

### Constraints

• $1\le �\le 100,000$
• $1\le �\le 1,000,000$

Subtask #1 (20 points): $1\le �,�\le 25$

Subtask #2 (80 points): original constraints

### Sample 1:

Input
Output
3
1
2
4
1
5
119

### Explanation:

Example case 1: $�=\left[1\right]$

Example case 2: $�=\left[1,2\right]\to \left[1+2+1\cdot 2\right]$

Example case 3: $�=\left[\mathbf{\text{1}},2,3,\mathbf{\text{4}}\right]\to \left[\mathbf{\text{2}},3,\mathbf{\text{9}}\right]\to \left[3,29\right]\to \left[119\right]$. The chosen elements in each step are in bold.

Code(C++):-

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long t;
cin >> t;
ll a[1000001];
for(int i=1;i<1000001;i++){
a[i]=(a[i-1]+i+(i*a[i-1]))%mod;
}
while (t--){
ll n;
cin>>n;
cout<<a[n]<< "\n";
}
return 0;
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class rtr {
public static int gcf(int a, int b) {
if (b == 0)
return a;
return gcf(b, a % b);
}

public static int lcm(int a, int b) {
return (a * b) / gcf(a, b);
}

public static void main(String[] args) throws java.lang.Exception {
Scanner input = new Scanner(System.in);
int test = input.nextInt();
long a[]=new long[1000_0001];
int i;
long m=1000_000_007;
for(i=1;i<a.length;i++)
{
a[i]=(a[i-1]+i+(i*a[i-1]))%m;
}
while (test > 0) {
int n = input.nextInt();
System.out.println(a[n]%m);
test--;
}
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-