402:整数値多項式

多項式$n^4 + 4n^3 + 2n^2 + 5n$はすべての整数$n$において6の倍数となることが示せる。 また、このような性質を満たす最大の整数は6であることも示せる。

$n^4 + an^3 + bn^2 + cn$がすべての整数$n$で$m$の倍数となるような最大の$m$を$M(a, b, c)$と定義しよう。例えば$M(4, 2, 5) = 6$となる。

同様に、$0 < a, b, c \leq N$のときの$M(a, b, c)$の和を$S(N)$と定義しよう。

$S(10) = 1972$、そして$S(10000) = 2024258331114$であることがわかる。

フィボナッチ数列$F_k$を次のように定義しよう：

$F_0 = 0, F_1 = 1$ そして$k \geq 2$のとき$F_k = F_{k-1} + F_{k-2}$

$2 \leq k \leq 1234567890123$に対する$\sum S(F_k)$の末尾9桁を求めよ。