**2 人解决**，5 人已尝试。

**2 份提交通过**，共有 7 份提交。

**9.2** EMB 奖励。

**单点时限: **5.0 sec

**内存限制: **256 MB

Simon Haples is a somewhat peculiar person. Not quite hip,not quite square, he is more of a triangular nature: ever since childhood, he has had an almost unhealthy obsession with

triangles. Because of his discrete nature, Simon’s favorite kind of triangles are the Pythagorean ones, in which the side lengths are three positive integers a, b, and c such that a ≤b and a^{2}+b^{2} = c^{2}.

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 nd all Pythagorean triples modulo n, i.e., all triples of integers a, b and c between 1 and n - 1 such that a ≤b and a^{2} + b^{2} = c^{2} (mod 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 ≤n ≤500 000.

Output the number of Pythagorean triples modulo n.

Input

7 /* 15 */

Output

18 /* 64 */

**2 人解决**，5 人已尝试。

**2 份提交通过**，共有 7 份提交。

**9.2** EMB 奖励。

题目标签