Upside Down is a modification of the famous Pythagorean equation: $$\begin{array}{r}\frac{1}{x^2}+\frac{1}{y^2}=\frac{13}{z^2}.\end{array}$$

A solution $(x,y,z)$ to this equation with $x,y$ and $z$ positive integers is a primitive solution if $gcd(x,y,z)=1$.

Let $S(N)$ be the sum of $x+y+z$ over primitive Upside Down solutions such that $1\le x,y,z\le N$ and $x\le y$.
For $N=100$ the primitive solutions are $(2,3,6)$ and $(5,90,18)$, thus $S({10}^2)=124$.
It can be checked that $S({10}^3)=1470$ and $S({10}^5)=2340084$.

Find $S({10}^{16})$ and give the last $9$ digits as your answer.