844 : kマルコフ数

方程式

$$a^2 + b^2 + c^2 = 3abc$$

の正の整数である解を考える。例えば $(1,5,13)$は解である。3マルコフ数を、いずれかの解に含まれる数と定義する。よって $1, 5, 13$ は3マルコフ数である。$10^3$ 以下の全ての3マルコフ数の和は2797である。

$k$マルコフ数を、次の方程式のいずれかの正整数解と定義する。

$$\sum_{i=1}^k {x_i}^2 = k \prod_{i=1}^k x_i, \; \; x_i は正整数$$

$M_k(N)$ を、$N$ 以下の $k$マルコフ数の和とする。よって $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}) \bmod 1\,405\,695\,061$ を求めよ。