It can be shown that the polynomial $n^4+4n^3+2n^2+5n$ is a multiple of $6$ for every integer $n$. It can also be shown that $6$ is the largest integer satisfying this property.

Define $M(a,b,c)$ as the maximum $m$ such that $n^4+a{n}^3+b{n}^2+cn$ is a multiple of $m$ for all integers $n$. For example, $M(4,2,5)=6$.

Also, define $S(N)$ as the sum of $M(a,b,c)$ for all $0<a,b,c\le N$.

We can verify that $S(10)=1972$ and $S(10000)=2024258331114$.

Let $F_k$ be the Fibonacci sequence:
$F_0=0$, $F_1=1$ and
$F_k=F_{k-1}+F_{k-2}$ for $k\ge 2$.

Find the last $9$ digits of $\sum S(F_k)$ for $2\le k\le 1234567890123$.