Lattice points in lattice cubes (noch nicht übersetzt)

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 10⁹.