Given an array A of N elements, a prime number P and an integer K. It is guaranteed all the elements in the array are distinct.
Find the number of pairs of indices (i,j) such that (1≤i<j≤N) and (A[i]+A[j])×(A[i]2+A[j]2))≡K mod P
Note: 1 based indexing is followed.
Input format
Output format
Print the number of pairs of indices which satisfy the given condition in a new line.
Constraints
2≤N≤1050≤K,A[i]≤P−12≤P≤105