Since the editorial is taking too long I would like to know if anyone could explain the solution for the large test case of powsums.

For the first test cases I used matrix exponentiation based on the recurrence relations of Newton’s identities. This solution worked on **O(n^2)** per query but required expensive pre calculation of **O(n^3)** (x30) step per test case and of course this would be too large to pass the larger test cases. I even thought of using a faster multiplication algorithm but it seemed more like an optimization and not really the intended solution.

I thought of 2 other approaches:

**1** - Computing the eigen decomposition so I could reduce the time complexity from cubic to quadratic.

**2** - Finding the roots of the polynomials so on each query I could compute the sums of powers directly.

But I failed, the articles on eigendecomposition are still hard to digest for me and had no success of finding/calculating the roots of the polynomials. The best I could do was to use Fermat’s little theorem to reduce the range of **xi** from **10e18** to **10e9**.