For any positive integer $n$, the $n$th weak Goodstein sequence $\{g_1,g_2,g_3,\dots \}$ is defined as:

• $g_1=n$
• for $k>1$, $g_k$ is obtained by writing $g_{k-1}$ in base $k$, interpreting it as a base $k+1$ number, and subtracting $1$.

The sequence terminates when $g_k$ becomes $0$.

For example, the $6$th weak Goodstein sequence is $\{6,11,17,25,\dots \}$:

• $g_1=6$.
• $g_2=11$ since $6={110}_2$, ${110}_3=12$, and $12-1=11$.
• $g_3=17$ since $11={102}_3$, ${102}_4=18$, and $18-1=17$.
• $g_4=25$ since $17={101}_4$, ${101}_5=26$, and $26-1=25$.

and so on.

It can be shown that every weak Goodstein sequence terminates.

Let $G(n)$ be the number of nonzero elements in the $n$th weak Goodstein sequence.
It can be verified that $G(2)=3$, $G(4)=21$ and $G(6)=381$.
It can also be verified that $\sum G(n)=2517$ for $1\le n<8$.

Find the last $9$ digits of $\sum G(n)$ for $1\le n<16$.