方程式

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

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

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

$D(n)$ を、桁の数字の和が素数であるような $n$ 番目の正の整数とする。 例えば、$D(61)=157, D(10^8)=403539364$ である。

$D(10^{16})$ を求めよ。