## Integer-valued polynomials

### Problem 402

Published on Saturday, 17th November 2012, 07:00 pm; Solved by 219; Difficulty rating: 55%
It can be shown that the polynomial `n`^{4} + 4`n`^{3} + 2`n`^{2} + 5`n` 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} + `c``n` 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` ≤ `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` ≥ 2.

Find the last 9 digits of Σ S(F_{k}) for 2 ≤ `k` ≤ 1234567890123.