IBM Ponder This #292 · August 2022

Safety dance

A dance show consists of four dancers, designated A, B, C, and D, who dance on a stage for $n$ units of time. However, due to safety concerns, they cannot all dance together; either a single dancer performs in the middle section, or two dancers dance on the right and left parts of the stage, respectively.

When on the sides of the stage, each dancer can dance for 1, 2, or 3 units of time before being replaced by a dancer currently not on the stage. A dancer in the middle section must be replaced in 1 unit of time, either by another dancer in the middle or two others in the side sections. Dancers cannot switch places on stage directly from one unit of time to the next.

As a last rule, if two dancers need to be replaced at the same time, they must be replaced by a single dancer in the middle.

Here’s an example of a dance arrangement that takes 8 units of time in total. The top row represents the dancer on the right side of the stage and the bottom row the dancer on the left side of the stage in any given column representing a unit of time, unless those values are identical, which indicates a dancer in the middle of the stage:

AABDACCC
CCCDABBA

The following arrangement is illegal: B and C start together after A and D finish; A moves directly from the left to the middle; and B and D exchange sides.

AABBBADB
BDCCAABD

There are 16 arrangements for n=1, 120 for n=2, and 17,342,172 for n=8. Compute larger counts modulo N=3141592653. For n=128, the count modulo N is 2,484,449,895.

Your goal: Compute the number of arrangements for n=2^24=16,777,216, modulo N=3141592653.

A bonus "*" for the count when n=2^256, modulo N=3141592653.

Solution

Best opened after a real attempt

To be added.