HMMT February, 2022

Solution:
Let $a_n$ be the number of such possibilities where there are $n$ $90^{\circ}$ turns. Note that $a_0 = 10$ and $a_1 = 11 \cdot 9$.

Now suppose $n = 2k$ 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 = 2k+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}$$