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).

Written by gamwe6 who lives and works in San Francisco building useful things. You should follow him on Twitter