对于任意正整数n，第n个弱Goodstein序列$g_1, g_2, g_3, \ldots$按如下方式定义：

$g_1=n$，对于$k>1$，将$g_{k-1}$写成k进制表示，然后将其视为k+1进制的数，再减去1，即为$g_k$，当某一项为0时序列终止。

例如，第6个弱Goodstein序列为$6, 11, 17, 25, \ldots$：

$g_1=6$。

$g_2=11$，因为$6=110_2$，而$110_3=12$，$12-1=11$。

$g_3=17$，因为$11=102_3$，而$102_4=18$，$18-1=17$。

$g_4=25$，因为$17=101_4$，而$101_5=26$，$26-1=25$。

以此类推。可以证明所有弱古德斯坦序列都会终止。

记$G(n)$为第n个弱Goodstein序列中的非零元素个数。可以验证$G(2)=3, G(4)=21, G(6)=381$，以及$\sum_{n=1}^8G(n)=2517$。

求$\sum_{n=1}^{16}G(n)$的最后9位数字。

本题难度:

解答

$G(1)$到$G(7)$的值可以在OEIS A266203中找到。

容易看出若$g_{k-1}=k+1$，那么$g_k$也等于$k+1$，而$g_{k+1}=k$，接下来每次减1，再经过k次可得0。

对每个初值n，将对应的上述k值记作$k_n$。$n=1$到7时的$k_n$可以直接计算，$8\le n < 12$和$12\le n < 15$时的$k_n$可以用该页面上所提供的引文信息递归计算。

最终结果是$173214653$。

m=10**9
	
def f(x) :
    s=x
    for i1 in range(1,x):
        s=(s*pow(2,s,m))%m
    return (s*pow(2,s,m)-3)%m

d=[0,0,0,2,3,4,6,8]

print (1+3+5+21+61+381+2045+sum(f(d[n-4]) for n in range(8,12))+sum(f(d[n-8]*(1 << d[n-8])) for n in range(12,16)))%m