Sequences with Nice Divisibility Properties

Let $S e q (n, k)$ be the number of positive-integer sequences ${a_{i}}_{1 \leq i \leq n}$ of length $n$ such that:

$n$ is divisible by $a_{i}$ for $1 \leq i \leq n$ , and
$n + a_{1} + a_{2} + \dots + a_{n}$ is divisible by $k$ .

Examples:

$S e q (3, 4) = 4$ , and the $4$ sequences are:
${1, 1, 3}$
${1, 3, 1}$
${3, 1, 1}$
${3, 3, 3}$

$S e q (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 $S e q (1111, 24)$ are $840643584$ .

Find the last nine digits of $S e q (1234567898765, 4321)$ .

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.