Переворот - это модификация знаменитого уравнения Пифагора: \begin{align} \frac{1}{x^2}+\frac{1}{y^2}=\frac{13}{z^2} \end{align}

Решение $(x,y,z)$ для этого уравнения при натуральных $x,y$ и $z$ является примитивным решением, если $\gcd(x,y,z)=1$.

Пусть $S(N)$ будет суммой $x+y+z$ всех примитивных перевернутых решений, таких что $1 \leq x,y,z \leq N$ и $x \le y$.
Для $N=100$ примитивными решениями являются $(2,3,6)$ и $(5,90,18)$, таким образом $S(10^2)=124$.
Можно проверить, что $S(10^3)=1470$ и $S(10^5)=2340084$.

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