A gozinta chain for $n$ is a sequence $\{1,a,b,\dots ,n\}$ where each element properly divides the next.
For example, there are eight distinct gozinta chains for $12$:
$\{1,12\}$, $\{1,2,12\}$, $\{1,2,4,12\}$, $\{1,2,6,12\}$, $\{1,3,12\}$, $\{1,3,6,12\}$, $\{1,4,12\}$ and $\{1,6,12\}$.

Let $S(n)$ be the sum of all numbers, $k$, not exceeding $n$, which have $252$ distinct gozinta chains.
You are given $S({10}^6)=8462952$ and $S({10}^{12})=623291998881978$.

Find $S({10}^{36})$, giving the last nine digits of your answer.