考虑以下可以递归应用于任何正整数 $n$ 的过程：

• 如果 $n=1$ 不执行任何操作并且进程停止，
• 如果 $n$ 可被 $7$ 除以 $7$，
• 否则添加 $1$。

将 $g(n)$ 定义为进程结束之前必须添加的 $1$ 的数量。例如：

<中心>$125\stackrel{+1}{\to }126\stackrel{÷7}{\to }18\stackrel{+1}{\to }19\stackrel{+1}{\to }20\stackrel{+1}{\to }21\stackrel{÷7}{\to }3\stackrel{+1}{\to }4\stackrel{+1}{\to }5\stackrel{+1}{\to }6\stackrel{+1}{\to }7\stackrel{÷7}{\to }1$。

添加了八个 $1$，因此 $g(125)=8$。类似地，$g(1000)=9$ 和 $g(10000)=21$。

定义 $S(N)=\sum _{n=1}^{N}g(n)$ 和 $H(K)=S\left(\frac{7^K-1}{11}\right)$。您获得了 $H(10)=690409338$。

求 $H({10}^9)$ 模 $1117117717$。