ProjectEuler 511 Sequences with nice d - 拼圖

511. Sequences with nice divisibility properties

https://projecteuler.net/problem=511

令Seq(n, k)為符合下列條件的數列{a_i}(1≦i≦n)的總數：

　‧對所有1≦i≦n，a_i都能整除n。

　‧k整除n + a_1 + a_2 + ... + a_n。

舉例來說：

Seq(3, 4) = 4，這四個數列分別為：

{1, 1, 3}
{1, 3, 1}
{3, 1, 1}
{3, 3, 3}

Seq(4,11) = 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。

請求出S(1234567898765, 4321)的末九位數。

--