Counting 2x2 Matrices with Determinant 1 mod N

Given a modulus N, count the number of 2 × 2 matrices

$$ M = \begin{pmatrix} a & b \\ c & d \end{pmatrix} $$

with entries \(a, b, c, d\) in \(\{0, 1, \ldots, N-1\}\) such that their determinant satisfies

$$ ad - bc \equiv 1 \pmod{N}. $$

You are required to compute the total count:

$$ \sum_{a=0}^{N-1}\sum_{b=0}^{N-1}\sum_{c=0}^{N-1}\sum_{d=0}^{N-1} \Big[ ad-bc \equiv 1 \pmod{N} \Big]. $$

Note: When \(N=1\), consider that any number is congruent modulo 1, therefore the only matrix available will have its determinant equivalent to 0, which is considered as 1 modulo 1. Hence, the answer is 1 for \(N=1\).

inputFormat

The input consists of a single integer N (\(1 \leq N \leq 10^9\) is assumed for this problem).

outputFormat

Output a single integer which is the number of 2 × 2 matrices with entries from \(0\) to \(N-1\) whose determinant is congruent to \(1 \pmod{N}\).

sample

1

1