При заворачивании нескольких кубов в бумагу намного эффективнее оборачивать их все вместе, а не оборачивать каждый индивидуально. Например, чтобы обернуть 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 \pmod {1\,000\,000\,007}$.

Найдите $G(10^{16})$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,007$.