7. 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.
Answer: $\quad 646634$
Solution: Let $a_{n}$ be the number of such possibilities where there $n 90^{\circ}$ turns. Note that $a_{0}=10$ and $a_{1}=11 \cdot 9$.
Now suppose $n=2 k$ with $k \geq 1$. The path traced out by the $s_{i}$ is uniquely determined by a choice of $k+1$ nonnegative $x$-coordinates and $k$ positive $y$-coordinates indicating where to turn and when to stop. If $n=2 k+1$, the path is uniquely determined by a choice of $k+1$ nonnegative $x$-coordinates and $k+1$ positive $y$-coordinates.
As a result, our final answer is
$$
10+11 \cdot 9+\binom{12}{2}\binom{9}{1}+\binom{12}{2}\binom{9}{2}+\cdots=-12+\binom{12}{0}\binom{9}{0}+\binom{12}{1}\binom{9}{0}+\binom{12}{1}\binom{9}{1}+\cdots .
$$

One can check that
$$
\sum_{k=0}^{9}\binom{12}{k}\binom{9}{k}=\sum_{k=0}^{9}\binom{12}{k}\binom{9}{9-k}=\binom{21}{9}
$$
by Vandermonde's identity. Similarly,
$$
\sum_{k=0}^{9}\binom{12}{k+1}\binom{9}{k}=\sum_{k=0}^{9}\binom{12}{k+1}\binom{9}{9-k}=\binom{21}{10} .
$$

Thus our final answer is
$$
\begin{aligned}
\binom{22}{10}-12 & =-12+\frac{22 \cdot 21 \cdot 2 \cdot 19 \cdot 2 \cdot 17 \cdot 2 \cdot 15 \cdot 2 \cdot 13}{6!} \\
& =-12+7 \cdot 11 \cdot 13 \cdot \frac{2^{5} \cdot 3^{2} \cdot 5 \cdot 19 \cdot 17}{2^{4} \cdot 3^{2} \cdot 5} \\
& =-12+1001 \cdot 2 \cdot 17 \cdot 19 \\
& =646646-12=646634 .
\end{aligned}
$$