Consider the following process that can be applied recursively to any positive integer $n$:

• if $n=1$ do nothing and the process stops,
• if $n$ is divisible by $7$ divide it by $7$,
• otherwise add $1$.

Define $g(n)$ to be the number of $1$'s that must be added before the process ends. For example:

$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$.

Eight $1$'s are added so $g(125)=8$. Similarly $g(1000)=9$ and $g(10000)=21$.

Define $S(N)=\sum _{n=1}^{N}g(n)$ and $H(K)=S\left(\frac{7^K-1}{11}\right)$. You are given $H(10)=690409338$.

Find $H({10}^9)$ modulo $1117117717$.