Divisibility by six conjecture for realized permutations

Let $a_{n,N}$ denote the number defined in the paper for permutations of length $n$ realized by the shift on an $N$-letter alphabet, with $n,N\geq 3$.

Divisibility by six conjecture. For every $n,N\geq 3$, $a_{n,N}$ is divisible by $6$.

The paper presents this as a striking empirical property of the computed values. Although an explicit formula for $a_{n,N}$ is available, the source says that this divisibility is not apparent from the formula and leaves the general assertion as a conjecture.