Efficient Evaluation of the Expression

Question

I have stumbled upon this problem and couldn't really get to an efficient approach :

Problem:
We have an array $P$ having $N$ elements denoted by $P_i$. Our task is to find the value of the below expression.

$$X=\sum_{j=1}^k \prod_{i=1}^N(P_i-j)$$ where $k$ is the minimum element in the array. We have to return the value of X modulo $10^9+7$.

Constraints:

$1 \le P_i \lt 10^9+7$
$ 1 \le N \le 10^5 $

The only solution that I have been able to come up with is a brute force approach of complexity $O(N\times K)$ where $K$ is the minimum element in the array. I think maybe something like FFT or generating functions could be used but I couldn't understand how.

Any sort of help is appreciated!!

Answer 1

Let $ f(x) = \prod_{i=1}^N (-1)( x - P_i) \sum_{i=0}^N a_i x^i$.

We want to calculate $ \sum_{x=1}^k f(x),$ which is a lot easier to do termwise with a change of variable, namely:

$$ = \sum_{x=1}^k \sum_{i=0}^N a_i x^i = \sum_{i=0}^N \left( a_i \sum_{x=1}^k x^i\right), $$

This is already quite a big simplification.
Note that $ \sum_{x=1}^k x^i$ could be further simplified via Faulbaher's formula.