Plot the Curve
Tag(s):

## Data Structures, Hash Maps, Hash Tables

Problem
Editorial
Analytics

You are given with integers $a, b, c, d, m$. These represent the modular equation of a curve $y^2 mod\ m = (ax^3+bx^2+cx+d)\ mod\ m$

Also, you are provided with an array $A$ of size $N$. Now, your task is to find the number of pairs in the array that satisfy the given modular equation.

If $(A_i, A_j)$ is a pair then $A_j^2 mod \ m = (aA_i^3+bA_i^2+cA_i+d)\ mod\ m$.

Since the answer could be very large output it modulo $10^9 + 7$.

Note: A pair is counted different from some other pair if either $A_i$ of the two pairs is different or $A_j$ of the two pairs is different. Also for the convenience of calculations, we may count $(A_i,A_i)$ as a valid pair if it satisfies given constraints.

Input Format
First line of the input contains number of test cases $T$.
First line for each test case consists of $5$ space-separated integers $a, b, c, d, m$, corresponding to modular equation given.
Next line contains a single integer $N$.
Next line contains $N$ space-separated integers corresponding to values of array $A$.

Output Format
For each test case, output a single line corresponding to number of valid pairs in the array mod $10^9+7$.

Constraints
$1 \le T \le 10\\ 1 \le N \le10^5\\ -2 \times10^9 \le a,b,c,d,A_i \le 2 \times 10^9\\ 1 \le m \le 2 \times 10^9$

SAMPLE INPUT
1
2 1 -1 3 5
5
10 2 3 14 12


SAMPLE OUTPUT
2

Explanation

Equation of curve: $y^2=2x^3+x^2-x+3$ and m$=5$.
Valid pairs satisfying equation of line are $(x,y) = (2,14)$ and $(12,14)$. Therefore, the answer is $2$.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Lenskart SDE1 & SDE2 Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Searching
• Data Structures > Arrays