# 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$$ を求めよ。









