Problem 875

Quadruple Congruence

For a positive integer $n$ we define $q(n)$ to be the number of solutions to:

$$a_1^2+a_2^2+a_3^2+a_4^2 \equiv b_1^2+b_2^2+b_3^2+b_4^2 \pmod n$$

where $0 \leq a_i, b_i \lt n$. For example, $q(4)= 18432$.

Define $\displaystyle Q(n)=\sum_{i=1}^{n}q(i)$. You are given $Q(10)=18573381$.

Find $Q(12345678)$. Give your answer modulo $1001961001$.

对于正整数$n$，定义$q(n)$为如下同余方程的解的数目：
$$a_1^2+a_2^2+a_3^2+a_4^2 \equiv b_1^2+b_2^2+b_3^2+b_4^2 \pmod n$$
其中$0 \leq a_i, b_i \lt n$。例如，$q(4)= 18432$。

定义$\displaystyle Q(n)=\sum_{i=1}^{n}q(i)$。已知$Q(10)=18573381$。

求$Q(12345678)$，并对$1001961001$取余作为你的答案。