Lessons from Count Good Numbers

$1.$ Counting problems often reduce to exponentiation. If each position has $k$ choices and positions are independent, total count is $k^n$.

$2.$ When $n$ is large ($> 10^6$), use modular exponentiation. Direct computation will overflow or time out.

$3.$ Ceiling and floor tricks for splitting positions: even positions = $(n + 1) / 2$, odd positions = $n / 2$ (integer division).