Решеточный куб - это куб, чьи все вершины имеют целочисленные координаты. Пусть C(n) будет количеством различных решеточных кубов, координаты вершин которых находятся в диапазоне от 0 до n (включительно). Здесь два куба считаются различными, если координаты не всех их вершин совпадают.
Например, C(1)=1, C(2)=9, C(4)=100, C(5)=229, C(10)=4469 и C(50)=8154671.

Различные кубы могут содержать разное количество точек сетки.

Например, куб с вершинами
(0, 0, 0), (3, 0, 0), (0, 3, 0), (0, 0, 3), (0, 3, 3), (3, 0, 3), (3, 3, 0), (3, 3, 3) содержит 64 точки сетки (56 точек сетки на поверхности, включая 8 вершин, и 8 точек внутри куба).

В свою очередь, куб с вершинами
(0, 2, 2), (1, 4, 4), (2, 0, 3), (2, 3, 0), (3, 2, 5), (3, 5, 2), (4, 1, 1), (5, 3, 3) содержит только 40 точек сетки (20 точек на поверхности и 20 точек внутри куба), хотя оба куба имеют одинаковую длину ребра 3.

Пусть S(n) будет суммой точек сетки, содержащихся в различных решеточных кубах, координаты всех вершин которых находятся в диапазоне от 0 до n (включительно).

Например, S(1)=8, S(2)=91, S(4)=1878, S(5)=5832, S(10)=387003 и S(50)=29948928129.

Найдите S(5000) mod 10⁹.