## Problem Links

**Author: ** Ankur Goel

**Tester: **Ankur Goel

**Editorialist:** Ankur Goel

## Difficulty

Medium

## Prerequisites

Factorial

## Problem

In a secret government project there are N investors who can invest X_{1},X_{2}.........X_{N} amount in millions such that X_{1},X_{2}.........X_{N} are all distinct i.e the amount they are ready to invest are different and the amount is not in fraction (i.e example X_{1}= 1 million is valid but X_{1}=1.5 million is invalid).There is a policy for forming groups among investors.Two investors who are ready to invest (suppose X_{1} and X_{2} amount individually) when grouped together,they feel confident and wish to invest more such that their total invested amount is equal to the sum of product of their individual investments added to their individual amount to be invested(i.e individually they could invest X_{1} and X_{2} amounts but after grouping together they can invest a total amount of X_{1}+X_{2}+X_{1}*X_{2}).Investors can further be combined with other investors and groups but by using the grouping policy mentioned before.

The Target is to find the maximum amount of money the government can fetch from the n investors.

## Quick Explanation

Ans= (Factorial(N+1)-1)%M

## Explanation

The Problem is simply based on the Factorial. Lets have a close look at this problem by with the help of an example.Let N=3, and X_{1}=1, X_{2}=2 and X_{3}=3. It does not matter which two of the investors should be grouped at any point of time because whichever two you group at any time, the final answer will be same.
Let us first group X_{1} and X_{2}

=> X(1,2)=1+2+1*2=5

Now Lets group X(1,2) and X_{3}

=> X(X(1,2),3) = X(5,3) = 5+3+5*3= 23 = Factorial(4)-1

In General for n investors, Ans= (Factorial(n+1)-1)%M

Use 64 bit int and take modulo at every step in calculating factorial to prevent the overflow.

# Author's Solution

Authorâ€™s solution can be found here