Problem 579
Lattice points in lattice cubes
A lattice cube is a cube in which all vertices have integer coordinates. Let C($n$) be the number of different lattice cubes in which the coordinates of all vertices range between (and including) 0 and $n$. Two cubes are hereby considered different if any of their vertices have different coordinates.
For example, C(1)=1, C(2)=9, C(4)=100, C(5)=229, C(10)=4469 and C(50)=8154671.
Different cubes may contain different numbers of lattice points.
For example, the cube with the vertices
(0, 0, 0), (3, 0, 0), (0, 3, 0), (0, 0, 3), (0, 3, 3), (3, 0, 3), (3, 3, 0), (3, 3, 3) contains 64 lattice points (56 lattice points on the surface including the 8 vertices and 8 points within the cube).
In contrast, the cube with the vertices
(0, 2, 2), (1, 4, 4), (2, 0, 3), (2, 3, 0), (3, 2, 5), (3, 5, 2), (4, 1, 1), (5, 3, 3) contains only 40 lattice points (20 points on the surface and 20 points within the cube), although both cubes have the same side length 3.
Let S($n$) be the sum of the lattice points contained in the different lattice cubes in which the coordinates of all vertices range between (and including) 0 and $n$.
For example, S(1)=8, S(2)=91, S(4)=1878, S(5)=5832, S(10)=387003 and S(50)=29948928129.
Find S(5000) mod 109.
格点立方体上的格点
格点立方体指的是顶点坐标均为整数的立方体。记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。
考虑所有顶点坐标在0和$n$（含）之间的不同格点立方体，记S($n$)为这些立方体所包含的格点的总数。
例如，S(1)=8，S(2)=91，S(4)=1878，S(5)=5832，S(10)=387003而S(50)=29948928129。
求S(5000) mod 109。