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{aligned} (1) & D (1) & = 1 \\ (2) & D (p) & = 1, for any prime p \\ (3) & D (p q) & = D (p) q + p D (q), for any positive integers p, q > 1. \end{aligned}$

Now let $a_{1}, a_{2}, \dots, 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{aligned} (4) & D (1) & = 1 \\ (5) & D (p) & = 1, 对于任意质数 p \\ (6) & D (p q) & = D (p) q + p D (q), 对于任意正整数 p, q > 1. \end{aligned}$

考虑 $n$ 的分拆 $a_{1}, a_{2}, \dots, 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$ 。