SP14700 DELTACA2 - Delta catheti II (Hard)

**(3, 4, 5)** is a famous Pythagorean triple, it gives a quick answer to the question: For a given integer **_d_**, is there a Pythagorean triple **(_a, b, c_)** such that **_b - a = d_**? A solution is **(3_d_, 4_d_, 5_d_)**, and in fact one can easily prove that the set of solutions is infinite, and that there is an obvious total order on those solutions. Given **_n_**, you'll have to find the **_n_**th term of the sequence of solutions. Geometrically, it is the study of right angle triangles for which the difference of the catheti is equal to **_d_**.

The first line of input contains an integer **_T_**, the number of test cases. **2_T_** lines follow. Each case is on two lines. The first line of the case contains three integers **_n, d, m_**. The second line contains an integer **_L_** and **2_L_** other integers (p, e) ; this gives the prime factorization of **_d_** in standard format (d = product p^e).

For each test case, compute the **_n_**th term amongst the solutions **(_a, b, c_)** for the problem : **_a $ ^{2} $ + b $ ^{2} $ = c $ ^{2} $_** with **_b - a = d_** and **_0 < a < b < c_** . As the answer could not fit in a 64-bit container, simply output your answer modulo **_m_**.