CodeChef- Chef and Strange Formula

For positive integer x let define function F(x) = 1 (1! + x) + 2 (2! + x) + .. + x * (x! + x).

"k!" 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 
#define M 10000000 

long long int factorial(long long int n)
{
    long long int i,fact=1;
    for(i=1;i<=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("%lld%lld",&n,&m);
    long long int i,p[n];
    for(i=0;i<n;i++)
    {
        scanf("%lld",&p[i]);
    }
    long long int sum=0;
    for(i=0;i<n;i++)
    {
        sum+=func(p[i]);
    }
    printf("%lld\n",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 < m*m < 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 < n; i++) {
        x = p[i];
        if (x < x0) return 0;
        a = x % m * x % m * ((x + 1) / 2 % m) % m;
        for (var k = x0 + 1; k <= 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.

StackExchange Code Review Q#87910, answer score: 4