Рассмотрим следующее диофантово уравнение: $$16x^2+y^4=z^2$$, где $x$, $y$ и $z$ - положительные целые числа.

Пусть $S(N) = \displaystyle{\sum(x+y+z)}$, где взята сумма всех решений $(x,y,z)$, таких что $1 \leq x,y,z \leq N$ и $\gcd(x,y,z)=1$.

Для $N=100$ существует только два таких решения: $(3,4,20)$ и $(10,3,41)$. Таким образом, $S(10^2)=81$.

Также известно, что $S(10^4)=112851$ (с 26 решениями) и $S(10^7)\equiv 248876211 \pmod{10^9}$.

Найдите $S(10^{16})$. В качестве ответа приведите остаток от деления полученного результата на $10^9$.