Рассмотрим все точки решетки (a, b, c) с 0 ≤ a, b, c ≤ N.

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

Вам дается, что D (1 000 000) = 831909254469114121.

Найдите D (1010). Дайте в качестве ответа первые девять цифр, за которыми следуют последние девять цифр.