AIME 2023a Problem 14

The following analog clock has two hands that can move independently of each other. [asy] unitsize(2cm); draw(unitcircle,black+linewidth(2)); for (int i = 0; i < 12; ++i) { draw(0.9dir(30i)--dir(30i)); } for (int i = 0; i < 4; ++i) { draw(0.85dir(90i)--dir(90i),black+linewidth(2)); } for (int i = 1; i < 13; ++i) { label("\small" + (string) i, dir(90 - i * 30) * 0.75); } draw((0,0)--0.6dir(90),black+linewidth(2),Arrow(TeXHead,2bp)); draw((0,0)--0.4dir(90),black+linewidth(2),Arrow(TeXHead,2bp)); [/asy] Initially, both hands point to the number $12$. The clock performs a sequence of hand movements so that on each movement, one of the two hands moves clockwise to the next number on the clock face while the other hand does not move. Let $N$ be the number of sequences of $144$ hand movements such that during the sequence, every possible positioning of the hands appears exactly once, and at the end of the $144$ movements, the hands have returned to their initial position. Find the remainder when $N$ is divided by $1000$.