Solution:

Record the hands as an ordered pair $(a, b) \in \mathbb{Z}_{12} \times \mathbb{Z}_{12};$ each movement replaces $(a, b)$ by $(a+1, b)$ or $(a, b+1),$ so a valid sequence is a closed tour through all $144$ positions — equivalently, a choice, at each position, of which hand moves next. Sort the positions into $12$ rows according to $b,$ and let $S_b \subseteq \mathbb{Z}_{12}$ be the set of $a$-values at which the tour leaves row $b$ (a $b$-move). A $b$-move from row $b - 1$ enters row $b$ at the same $a$-value, and the tour then runs through consecutive $a$-values until its next exit. For these runs to cover row $b$ exactly once they must partition $\mathbb{Z}_{12},$ which forces each entry point to sit one step past an exit: $S_{b-1} = S_b + 1.$ In particular every $S_b$ has the same size $c,$ and $S_b = S_0 - b.$

Leaving row $b$ at its $i$-th exit (in cyclic order) leads to a run ending at the $(i+1)$-st exit of row $b + 1:$ each $b$-move advances the row index by $1$ modulo $12$ and the exit index by $1$ modulo $c.$ The tour therefore closes after $\operatorname{lcm}(12, c)$ $b$-moves, while a full tour must use all $12c$ exits, so the tour is a single cycle through all $144$ positions precisely when $\gcd(c, 12) = 1.$ Conversely, every choice of $S_0$ with $\gcd(|S_0|, 12) = 1$ yields exactly one valid movement sequence from the starting position.

Hence $$N = \binom{12}{1} + \binom{12}{5} + \binom{12}{7} + \binom{12}{11} = 12 + 792 + 792 + 12 = 1608,$$ and the remainder when $N$ is divided by $1000$ is $608.$