Time is ticking
Source: 2023 AIME I Problem 14
February 8, 2023
AMCAIMEAIME I
Problem Statement
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.9*dir(30*i)--dir(30*i));
}
for (int i = 0; i < 4; ++i) {
draw(0.85*dir(90*i)--dir(90*i),black+linewidth(2));
}
for (int i = 0; i < 12; ++i) {
label("\small" + (string) i, dir(90 - i * 30) * 0.75);
}
draw((0,0)--0.6*dir(90),black+linewidth(2),Arrow(TeXHead,2bp));
draw((0,0)--0.4*dir(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 while the other hand does not move.Let 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 is divided by 1000.