---

Problem 748

---

Upside down Diophantine equation

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

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.

---

颠倒不定方程

把著名的毕达哥拉斯方程稍加修改就得到了如下的颠倒不定方程：
$$\frac{1}{x^2}+\frac{1}{y^2}=\frac{13}{z^2}$$

若上述方程的一组正整数解$(x,y,z)$满足$gcd(x,y,z)=1$，则称之为该方程的本原解。

考虑该方程的所有本原解，并记$S(N)$为所有满足$1\le x,y,z\le N$和$x\le y$的本原解对应$x+y+z$之和。
对于$N=100$，满足条件的本原解包括$(2,3,6)$和$(5,90,18)$，因此$S({10}^2)=124$。
可以验证，$S({10}^3)=1470$，$S({10}^5)=2340084$。

求$S({10}^{16})$，并给出最后$9$位数字作为你的答案。

---