For the 20% subtask, run the prefix sum array algorithm on the array ~M~ times.

In order to get 100% of the points, notice that if we try to solve this problem for a general array, the coefficients of the original array values produce a diagonal cut of Pascal's triangle. Thus, we need a fast way to generate combinations.

The combinations needed are:

$$\displaystyle \binom{M}{0}, \binom{M+1}{1}, \binom{M+2}{2}, \binom{M+3}{3}, \binom{M+4}{4}, \dots, \binom{M+N-1}{N-1}$$

The first coefficient is always ~1~ (since ~\dbinom{M}{0} = 1~). Then, by using the formula given in P4, ~coeff[i] = \dfrac{coeff[i-1] \times (M+i)}{i}~. The last challenge is to divide by ~i~; we must instead multiply by the inverse of ~i~. The inverse of ~i~ is some other integer ~j~ such that ~(i \times j) \equiv 1 \pmod{10^9+7}~. The reason is that ~(A \times i \times B) \times j \equiv (A \times B) \times (i \times j) \equiv A \times B \pmod{10^9+7}~ which gets rid of the number ~i~; this has the same effect as division.

From Fermat's Little Theorem, ~a^{p-1} \equiv 1 \pmod p~ if ~p~ is prime. Since ~10^9+7~ is prime, we can see that ~i \times i^{10^9+7-2} \equiv 1~. Thus, the inverse of ~i~ is ~i^{10^9+5}~. Again, the quick power algorithm must be used.

After generating the first ~N~ coefficients, the rest of the problem should be trivial to solve.

Time complexity: ~\mathcal{O}(N^2)~

Bonus: Given ~M~ and the output array, can you quickly find the input array?