Eccoci.

Consider the following Diophantine equation: $$16x^2+y^4=z^2$$ where $x$, $y$ and $z$ are positive integers.

Let $S(N) = \displaystyle{\sum(x+y+z)}$ where the sum is over all solutions $(x,y,z)$ such that $1 \leq x,y,z \leq N$ and $\gcd(x,y,z)=1$.

For $N=100$, there are only two such solutions: $(3,4,20)$ and $(10,3,41)$. So $S(10^2)=81$.

You are also given that $S(10^4)=112851$ (with 26 solutions), and $S(10^7)\equiv 248876211 \pmod{10^9}$.

Find $S(10^{16})$. Give your answer modulo $10^9$.