Problem 618

Numbers with a given prime factor sum

Consider the numbers 15, 16 and 18:
$15=3\times5$ and $3+5=8$.
$16=2\times2\times2\times2$ and $2+2+2+2=8$.
$18=2\times3\times3$ and $2+3+3=8$.
15, 16 and 18 are the only numbers that have 8 as sum of the prime factors (counted with multiplicity).

We define $S(k)$ to be the sum of all numbers $n$ where the sum of the prime factors (with multiplicity) of $n$ is $k$.
Hence $S(8)=15+16+18=49$.
Other examples: $S(1)=0$, $S(2)=2$, $S(3)=3$, $S(5)=5+6=11$.

The Fibonacci sequence is $F_1=1$, $F_2=1$, $F_3=2$, $F_4=3$, $F_5=5$, $\ldots$
Find the last nine digits of $\sum_{k=2}^{24}S(F_k)$.

给定质因数和的整数

考虑整数15，16和18的质因数分解：
$15=3\times5$，而$3+5=8$。
$16=2\times2\times2\times2$，而$2+2+2+2=8$。
$18=2\times3\times3$，而$2+3+3=8$。
15，16和18是仅有的质因数和（包括重复）为8的整数。

记$S(k)$为所有质因数和（包括重复）为$k$的整数$n$的和。
因此$S(8)=15+16+18=49$。
其它例子包括：$S(1)=0$，$S(2)=2$，$S(3)=3$，$S(5)=5+6=11$。

考虑斐波那契数列$F_1=1$，$F_2=1$，$F_3=2$，$F_4=3$，$F_5=5$，$\ldots$
求$\sum_{k=2}^{24}S(F_k)$的最后九位数字。