Для положительного целого числа $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$.