---

Problem 511

---

Sequences with nice divisibility properties

Let Seq(n,k) be the number of positive-integer sequences {a_i}_1≤i≤n of length n such that:

• n is divisible by a_i for 1 ≤ i ≤ n, and
• n + a₁ + a₂ + … + a_n is divisible by k.

Examples:

Seq(3,4) = 4, and the 4 sequences are:
{1, 1, 3}
{1, 3, 1}
{3, 1, 1}
{3, 3, 3}

Seq(4,11) = 8, and the 8 sequences are:
{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}

The last nine digits of Seq(1111,24) are 840643584.

Find the last nine digits of Seq(1234567898765,4321).

---

拥有良好可整除性的数列

记Seq(n,k)是所有满足下列条件的长为n的正整数序列{a_i}_1≤i≤n的数目：

• 对于所有1 ≤ i ≤ n，n能够被a_i整除，且
• n + a₁ + a₂ + … + a_n能被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)的最后九位数字。

---