HMMT 2022 C7

Let $S=\left\{(x, y) \in \mathbb{Z}^{2} \mid 0 \leq x \leq 11,0 \leq y \leq 9\right\}$. Compute the number of sequences $\left(s_{0}, s_{1}, \ldots, s_{n}\right)$ of elements in $S$ (for any positive integer $n \geq 2$ ) that satisfy the following conditions:

• $s_{0}=(0,0)$ and $s_{1}=(1,0)$,
• $s_{0}, s_{1}, \ldots, s_{n}$ are distinct,
• for all integers $2 \leq i \leq n, s_{i}$ is obtained by rotating $s_{i-2}$ about $s_{i-1}$ by either $90^{\circ}$ or $180^{\circ}$ in the clockwise direction.