Рассмотрим значения $\log_2(8)$, $\text{log}_4(64)$ и $\text{log}_3(27)$. Все три равны $3$.

Вообще, функция $f(m,n)=\text{log}_m(n)$ от целых чисел $m,n \ge 2$ имеет свойство
$f(m_1,n_1)=f(m_2,n_2)$, если

1. $\, m_1=a^e, n_1=a^f, m_2=b^e,n_2=b^f \,$ для целых чисел $a,b,e,f \, \,$ или
2. $ \, m_1=a^e, n_1=b^e, m_2=a^f,n_2=b^f \,$ для целых чисел $a,b,e,f \,$

Назовем функцию $g(m,n)$ от целых чисел $m,n \ge 2$ прото-логарифмической, если

• $\quad \, \, \, \, g(m_1,n_1)=g(m_2,n_2)$, если существуют целые числа $a,b,e,f$, удовлетворяющие условию №1 или №2
• и $\, g(m_1,n_1) \ne g(m_2,n_2)$, если не существуют целые числа $a,b,e,f$, удовлетворяющие условию №1 или №2

Пусть $D(N)$ будет количеством различных значений, которые любая прото-логарифмическая функция $g(m,n)$ принимает при $2\le m, n\le N$.
Например, $D(5)=13$, $D(10)=69$, $D(100)=9607$ и $D(10000)=99959605$.

Найдите $D(10^{18})$ и приведите в качестве ответа последние 9 цифр полученного числа.

Примечание: Согласно гипотезе четырех экспонент, функция $\text{log}_m(n)$ является прото-логарифмической.
Несмотря на то, что эта гипотеза до сих пор не доказана в общем случае, можно использовать $\text{log}_m(n)$ для вычисления $D(N)$ при небольших значениях $N$.