---

Problem 840

---

Sum of Products

A partition of $n$ is a set of positive integers for which the sum equals $n$.

The partitions of $5$ are:

$\{5\},\{1,4\},\{2,3\},\{1,1,3\},\{1,2,2\},\{1,1,1,2\}$ and $\{1,1,1,1,1\}$.

Further we define the function $D(p)$ as:
$$
\begin{align}
D(1) & = 1 \\
D(p) & = 1, \text{ for any prime } p \\
D(pq) & = D(p)q + pD(q), \text{ for any positive integers } p,q > 1.
\end{align}
$$

Now let ${a_1, a_2,\ldots,a_k}$ be a partition of $n$.

We assign to this particular partition the value:
$$P=\prod_{j=1}^{k}D(a_j). $$

$G(n)$ is the sum of $P$ for all partitions of $n$.

We can verify that $G(10) = 164$.

We also define:
$$S(N)=\sum_{n=1}^{N}G(n).$$
You are given $S(10)=396$.

Find $S(5\times 10^4) \mod 999676999$.

---

乘积之和

$n$的一个分拆是指一组无序且和为$n$的正整数。

例如，$5$的分拆包括：

$\{5\}$、$\{1,4\}$、$\{2,3\}$、$\{1,1,3\}$、$\{1,2,2\}$、$\{1,1,1,2\}$和$\{1,1,1,1,1\}$。

进一步定义函数$D(p)$如下：
$$
\begin{align}
D(1) & = 1 \\
D(p) & = 1, \text{对于任意质数} p \\
D(pq) & = D(p)q + pD(q), \text{对于任意正整数} p,q > 1.
\end{align}
$$

考虑$n$的分拆${a_1, a_2,\ldots,a_k}$。

这一分拆的得分是：
$$P=\prod_{j=1}^{k}D(a_j)$$

记$G(n)$为$n$的所有分拆的得分$P$之和。

可以验证$G(10) = 164$。

再定义：
$$S(N)=\sum_{n=1}^{N}G(n)$$
已知$S(10)=396$。

求$S(5\times 10^4) \mod 999676999$。

---