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(\mathrm{mod}n)$$

where $0\le a_i,b_i<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$.