Recently, Simon has discovered the fantastic world of counting modulo some integer $n$. As you may imagine, he quickly realizes that there are multitudes of Pythagorean triples to which he has previously been oblivious! Simon therefore sets out to find all Pythagorean triples modulo $n$, i.e., all triples of integers $a$, $b$ and $c$ between $1$ and $n-1$ such that $a \le b$ and $a^2 + b^2 \equiv c^2 \pmod{n}$.
As Simon’s best friend, you realize that there is not much hope in deterring Simon from his crazy plans, so you decide to help him by computing how many such triples there are, so that Simon will know when his work is done.
The input consists of a single integer $n$, satisfying $2 \le n \le 500\, 000$.
Output the number of Pythagorean triples modulo $n$.
Sample Input 1 | Sample Output 1 |
---|---|
7 |
18 |
Sample Input 2 | Sample Output 2 |
---|---|
15 |
64 |