CodeChef- Chef and Strange Formula For positive integer x let define function F(x) = 1 * (1! + x) + 2 * (2! + x) + .. + x * (x! + x).
&quot;k!&quot; means factorial: k! = 1 * 2 * .. * k
Chef wants to calculate F(p1) + F(p2) + ... + F(pn).
As answer could be large, help him, calculate value modulo m.

Input

First line contains two integers n and m.
Next line contains n space separated integers pi.

Output

Output a single line containing one integer --- calculated value modulo m.

Constraints
1 ≤ n ≤ 10^5
1 ≤ pi ≤ 10^18
1 ≤ m ≤ 10^7

Subtasks
Subtask #1: 1 ≤ pi ≤ 6 (10 points)
Subtask #2: 1 ≤ pi ≤ 7 * 10^3 (25 points)
Subtask #3: m - prime number (25 points)
Subtask #4: original constraints (40 points)

Here is my code
#include &lt;stdio.h&gt;
#define M 10000000 

long long int factorial(long long int n)
{
    long long int i,fact=1;
    for(i=1;i&lt;=n;i++)
        fact=((fact%M)*(i%M))%M;
    return fact;
}
long long int func(long long int n)
{
    long long int a=((n%M)*(n%M)*((n+1)%M))%M/2;
    long long int sum=(a+factorial(n+1)-1)%M;
    return sum;
}

int main()
{
    long long int n,m;
    scanf(&quot;%lld%lld&quot;,&amp;n,&amp;m);
    long long int i,p[n];
    for(i=0;i&lt;n;i++)
    {
        scanf(&quot;%lld&quot;,&amp;p[i]);
    }
    long long int sum=0;
    for(i=0;i&lt;n;i++)
    {
        sum+=func(p[i]);
    }
    printf(&quot;%lld\n&quot;,sum%m);
    return 0;
}

My code exceeds time limit on subtasks 2,3 and 4. How do I improve efficiency?
As youself noted F(x) can be reduced to:

x*x*(x+1)/2 + (x+1)! - 1


As @Daniel Sokolov pointed, you don't need to calculate full factorial for each p[i]. If p is a sorted array, you can use previously calculated factorial in the current (x+1)! calculation.

Furthermore it would be better to get modulo after each arithmetic operation. This ensure that the current result after each operation will always &lt; m*m &lt; 10^14.

So the code might look like this:

/**
 *  @param m modulo
 *  @param n number of integers
 *  @param p sorted array of integers
 *  @return sum of F(pn) series modulo m
*/
function sum(unsigned long m, unsigned n, unsigned long long int *p) {
    unsigned long long int
        x, // current element of p array
        x0 = 1, // previous element of p array
        a, // sum of arithmetic progression
        fac = 1, // factorial of (x + 1)
        ret = 0; // result
    for (unsigned i = 0; i &lt; n; i++) {
        x = p[i];
        if (x &lt; x0) return 0;
        a = x % m * x % m * ((x + 1) / 2 % m) % m;
        for (var k = x0 + 1; k &lt;= x + 1; k++)
            fac = fac * (k % m) % m;
        ret = ((ret + a) % m + fac - 1) % m;
        x0 = x;
    }
    return ret;
}


Note that it assumes p is a sorted array.