Разбиением числа $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} \begin{split} D(1) &= 1 \\ D(p) &= 1, \text{ для любого простого числа } p \\ D(pq) &= D(p)q + pD(q), \text{ для любых положительных целых чисел } p,q >1. \end{split} \end{align} $$

Пусть $\{a_1, a_2,\ldots,a_k\}$ будет разбиением числа $n$.
Присвоим этому конкретному разбиению значение:
$$P=\prod_{j=1}^{k}D(a_j). $$

$G(n)$ равно сумме $P$ для всех разбиений числа $n$.
Можно показать, что $G(10) = 164$.

Также определим: $$S(N)=\sum_{n=1}^{N}G(n).$$ Известно, что $S(10)=396$.
Найдите $S(5\times 10^4) \mod 999676999$.