Расммотрим целые положительные решения уравнения

Например, $(1,5,13)$ является таким решением. Определим 3-число Маркова как любую из частей решения. Таким образом $1$, $5$ и $13$ являются 3-числами Маркова. Сумма всех уникальных 3-чисел Маркова $\le 10^3$ равна $2797$.

Определим $k$-число Маркова как положительное целое число, которое является частью решения уравнения

Пусть $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})$. В качестве ответа приведите остаток от деления полученного результата на $1\,405\,695\,061$.