Consider the numbers $15$, $16$ and $18$:
$15=3\times 5$ and $3+5=8$.
$16=2\times 2\times 2\times 2$ and $2+2+2+2=8$.
$18=2\times 3\times 3$ 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$, ....
Find the last nine digits of ${\displaystyle \sum _{k=2}^{24}S(F_k)}$.