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\le x,y,z\le 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(\mathrm{mod}{10}^9)$.

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