考虑以下丢番图方程： $$16x^2+y^4=z^2$$ 其中 $x$、$y$ 和 $z$ 是正整数。

设 $S(N)={\displaystyle \sum (x+y+z)}$，其中所有解 $(x,y,z)$ 的总和使得 $1\le x,y,z\le 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(\mathrm{mod}{10}^9)$。

求$S({10}^{16})$。以 ${10}^9$ 为模给出你的答案。