Может быть показано, что многочлен n⁴ + 4n³ + 2n² + 5n является кратным 6 для каждого целого n. Также может быть показано, что 6 - самое большое целое число, имеющее такое свойство.

Определим M(a, b, c) как максимальное m, такое, что n⁴ + an³ + bn² + cn является кратным m для всех целых n. Например, M(4, 2, 5) = 6.

Также определим S(N) как сумму M(a, b, c) для всех 0 < a, b, c ≤ N.

Мы можем убедиться, что S(10) = 1972 и S(10000) = 2024258331114.

Пусть F_k будет последовательностью Фибоначчи:
F₀ = 0, F₁ = 1 и
F_k = F_k-1 + F_k-2 для k ≥ 2.

Найдите последние 9 цифр Σ S(F_k) для 2 ≤ k ≤ 1234567890123.