对于正整数 $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(\mathrm{mod}n)$$

其中 $0\le a_i,b_i<n$。例如，$q(4)=18432$。

定义${\displaystyle Q(n)=\sum _{i=1}^{n}q(i)}$。您将获得 $Q(10)=18573381$。

查找$Q(12345678)$。以 $1001961001$ 为模给出你的答案。