Рассмотрим все точки трехмерной сетки (a,b,c), где 0 ≤ a,b,c ≤ N.

Из начала координат O(0,0,0) проводятся прямые линии к каждой точке сетки.
Пусть D(N) будет количеством различных линий, полученных таким образом.

Дано, что D(1 000 000) = 831909254469114121.

Найдите D(10¹⁰). В качестве ответа приведите число, состоящее из первых девяти и последних девяти цифр полученного результата.