Задача 511
Последовательности с хорошими свойствами делимости

Пусть Seq(n,k) будет количеством последовательностей положительных целых чисел {ai}1≤i≤n длиной n, таких что:

  • n делится на ai для 1 ≤ i ≤ n, и
  • n + a1 + a2 + ... + an делится на k.

Примеры:

Seq(3,4) = 4, и 4 последовательности будут:
{1, 1, 3}
{1, 3, 1}
{3, 1, 1}
{3, 3, 3}

Seq(4,11) = 8, и 8 последовательностей будут:
{1, 1, 1, 4}
{1, 1, 4, 1}
{1, 4, 1, 1}
{4, 1, 1, 1}
{2, 2, 2, 1}
{2, 2, 1, 2}
{2, 1, 2, 2}
{1, 2, 2, 2}

Последние девять цифр Seq(1111,24) - это 840643584.

Найдите последние девять цифр Seq(1234567898765,4321).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net