I'm trying to solve https://www.codechef.com/problems/COOLSBST on codechef, I tried to think of solution that involves precomuting and square decomposition or sorting the test cases based on L and R but couldn't figure it out. can somebody explain how to solve it using square decomposition? thanks in advance.

I'm trying to solve Power sum on codechef https://www.codechef.com/SEPT19A/problems/PSUM, the problem can be solved using Dp and NTT. however when I viewed the submissions I noticed that the solution involves using the power series, can somebody please explain the intuition behind the solution and why do we use the power series? thats one of the submissions to the problem https://www.codechef.com/viewsolution/26607700 .