### PROBLEM LINK:

**Author:** Antoniuk Vasyl

**Tester:** Pushkar Mishra

**Editorialist:** Florin Chirica

### PROBLEM

Calculate the given sum.

### QUICK EXPLANATION

Let F(x) = (1 * 1! + 2 * 2! + .... + x * x!) + (1 * x + 2 * x + .... + x * x)

For the first bracket, it’s enough to calculate up to M, because i * i! = 0, for i \ge M.

For the second bracket, we can use well known formula that 1 + 2 + ... + x = \frac{x (x + 1)}{2} We need to perform division before considering modulo operation.

### EXPLANATION

**Breaking the sum into two parts**

When dealing with sums, a good idea is to “break” it. We can write F(x) as

F(x) = (1 * 1! + 2 * 2! + .... + x * x!) + (1 * x + 2 * x + .... + x * x)

The sums still look complicated. The trick here is to use the fact that modulo is reasonably small. Let’s calculate each bracket independently.

**Sum of i * i!**

Let’s recall definition of i!. i! = 1 * 2 * ... * i What happens if i \ge M (the modulo)? Then, obviously, term M will appear in the product. Since we calculate the expression modulo M, it’s like adding 0 element to the product (0 is equal to M modulo M). So, i! = 0, for i >= M. It immediately follows that i * i! = 0, for i \ge M.

Let’s store the sum of 1 * 1! + 2 * 2! + .... x * x! for each x \le M. We can compute it in \mathbb{O}(M). For each x \ge M, sum 1 * 1! + 2 * 2! + ... + x * x! is exactly 1 * 1! + 2 * 2! + ... + (M-1) * (M-1)!, since all the other terms are 0.

Alternatively, one can notice that 1 * 1! + 2 * 2! + ... + x * x! = (x+1)! - 1. This can easily be proven by mathematical induction.

**Sum of i * x**

Sum 1 * x + 2 * x + ... + x * x is in fact x * (1 + 2 + ... + x). We know that 1 + 2 + ... + x = \frac{x (x + 1)}{2}. So we get that the sum is \frac{x^2 \, (x + 1)}{2}. Since numbers x are up to 10^{18}, we might have a problem with the overflow. Moreover, we have to handle division by 2 somehow.

Let’s handle division by 2 firstly. One of the numbers x and x + 1 will be even. This means we can divide it by 2. Now the task is reduced to multiply 3 numbers, which can be up to 10^{18}.

We can use modulo properties once again. We know that (A * B) \,mod\, M = ((A\, mod\, M) * (B\, mod\, M))\, mod\, M. This means, we can reduce the task to multiply 3 numbers up to 10^7 (the modulo value) by doing modulo M for each of the numbers before multiplication.

This step is computed in \mathbb{O}(1), so the total complexity is \mathbb{O}(M + N).