考虑正整数解

<中心>$a^2+b^2+c^2=3abc$

例如，$(1,5,13)$就是一个解决方案。我们将 3-马尔可夫数定义为解的任何部分，因此 $1$、$5$ 和 $13$ 都是 3-马尔可夫数。添加不同的 3-马尔可夫数 $\le {10}^3$ 将得到 $2797$。

现在我们将 $k$-Markov 数定义为一个正整数，它是以下问题解决方案的一部分：

<中心>${\displaystyle \sum _{i=1}^k{x}_i^2=k\prod _{i=1}^k{x}_i,x_i\text{ are positive integers}}$

令 $M_k(N)$ 为 $k$-马尔可夫数 $\le N$ 的总和。因此$M_3({10}^3)=2797$，也是$M_8({10}^8)=131493335$。

定义 ${\displaystyle S(K,N)=\sum _{k=3}^K{M}_k(N)}$。您获得了 $S(4,{10}^2)=229$ 和 $S(10,{10}^8)=2383369980$。

查找 $S({10}^{18},{10}^{18})$。以 $1405695061$ 为模给出您的答案。