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$.