**PROBLEM LINK:** Practice, Contest

**CATEGORY:** EASY-MEDIUM

**PRE-REQUISITES:** Modulo Concepts.

**PROBLEM:**

You need to solve the A.G.P :

\left \{ \sum_{i=0}^{n}\left ( \left [ a+i\cdot d \right ] \cdot x^{n-i}\right ) \right \} mod \ 215372682525

**EXPLAINATION:**

It is a simple mathematics question. Here, you need to calculate the sum mod 215372682525 as mentioned above. But, keep in mind that 215372682525^2 = 46385392378014440375625, which is greater than 2^64. Therefore, all you need to do is calculate the value of x^0, x^1, x^2, x^3, x^4, …, x^n and simultaneously take the mod with 215372682525 and save the mod value at corresponding index i. Similarly, do the same for a + i*d for each value of i and save the mod value at corresponding index i. Now, multiply a + i*d with the corresponding x^(n-i) value and take the mod and save the mod value at corresponding index i. Finally, add them and simultaneously take the mod.

**C++ CODE:**

Link

**Author:** Suraj Singh

**Tester:** Naman Taneja

**Editorialist:** Suraj Singh