---

Problem 775

---

Saving Paper

When wrapping several cubes in paper, it is more efficient to wrap them all together than to wrap each one individually. For example, with $10$ cubes of unit edge length, it would take $30$ units of paper to wrap them in the arrangement shown below, but $60$ units to wrap them separately.

Define $g(n)$ to be the maximum amount of paper that can be saved by wrapping $n$ identical $1\times 1\times 1$ cubes in a compact arrangement, compared with wrapping them individually. We insist that the wrapping paper is in contact with the cubes at all points, without leaving a void.

With $10$ cubes, the arrangement illustrated above is optimal, so $g(10)=60-30=30$. With $18$ cubes, it can be shown that the optimal arrangement is as a $3\times 3\times 2$, using $42$ units of paper, whereas wrapping individually would use $108$ units of paper; hence $g(18)=66$.

Define
$$G(N)=\sum _{n=1}^{N}g(n)$$
You are given that $G(18)=530$, and $G({10}^6)\equiv 951640919(\mathrm{mod}1000000007)$.

Find $G({10}^{16})$. Give your answer modulo $1000000007$.

---

节约用纸

在包装多个立方体时，将它们放在一起包装比起分别包装更省纸张。例如，如果有$10$个单位边长的立方体，按照如下方式堆叠后只需要$30$单位面积的包装纸，而将它们分别包装则需要$60$单位面积的包装纸。

记$g(n)$为包装$n$个$1\times 1\times 1$大小的立方体时，采用最紧凑的方式包装相比分别包装最多能省下多少单位面积的包装纸。我们要求包装纸必须和立方体紧密贴合，不能留出空隙。

包装$10$个立方体时，如上所示的包装方式是最优的，因此$g(10)=60-30=30$。包装$18$个立方体时，可以证明最优的包装方式是将其堆叠为$3\times 3\times 2$大小，此时需要$42$单位面积的包装纸，而分别包装则需要$108$单位面积的包装纸，因此$g(18)=66$。

进一步定义
$$G(N)=\sum _{n=1}^{N}g(n)$$
已知$G(18)=530$，$G({10}^6)\equiv 951640919(\mathrm{mod}1000000007)$。

求$G({10}^{16})$，并将你的答案对$1000000007$取余。

---