晶格立方体是所有顶点都有整数坐标的立方体。令 $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}^9$。