## Sequences with nice divisibility properties

### Problem 511

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`for 1 ≤_{i}`i`≤`n`, and`n`+`a`_{1}+`a`_{2}+ ... +`a`is divisible by_{n}`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).