---

Problem 606

---

Gozinta Chains II

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⁶)=8462952 and S(10¹²)=623291998881978.

Find S(10³⁶), giving the last nine digits of your answer.

---

因子链II

n的因子链指的是一个序列{1,a,b,…,n}，其中每个元素都整除后一个元素。
例如，12有八条因子链：
{1,12}，{1,2,12}，{1,2,4,12}，{1,2,6,12}，{1,3,12}，{1,3,6,12}，{1,4,12}和{1,6,12}。

对于任意n，将所有不超过于n且恰好有252条不同因子链的整数k的和记为S(n)。
已知S(10⁶)=8462952，而S(10¹²)=623291998881978。

求S(10³⁶)，并给出其最后九位数字。

---