## Gozinta Chains II

### Problem 606

A **gozinta chain** for `n` is a sequence {1,a,b,...,`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.