21.1.13 ** There are $n$ parking spaces along a road, and $n$ drivers each driving a car. Each driver parks their car in front of their favorite parking space. If that space is already occupied, they park in the nearest available space down the road. If that space and all the spaces below it are occupied, they drive away without parking. Question: How many arrays $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ are there such that no parking space is empty? Here, $a_{i}$ is the favorite parking space of the $i$-th driver, and $a_{1}, a_{2}, \cdots, a_{n}$ do not have to be distinct.
There are $(n+1)^{n-1}$ arrays that satisfy the conditions.
For any array $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ that satisfies the conditions, define an associated array $\left(b_{2}, \cdots, b_{n}\right)$. Here, $b_{i}$ is the difference between the $i$-th driver's intended parking spot and the parking spot of the previous driver (i.e., the $(i-1)$-th driver), with the difference taken modulo $(n+1)$. Clearly, two different arrays $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ correspond to different associated arrays.

Next, we prove that for any array $\left(b_{2}, \cdots, b_{n}\right), b_{i} \in\{0,1, \cdots, n\}$, there is an array that satisfies the conditions with it as the associated array.

Imagine $n$ parking spots arranged in a circle, with the last position (the $(n+1)$-th position) being a virtual spot. Place the first driver in any position. For $i=2, \cdots, n$, the $i$-th driver parks in the next available spot that is $b_{i}$ positions away from the spot where the $(i-1)$-th driver parked. The array $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ satisfies the conditions if and only if the last empty spot is the virtual spot. Note that by rotating the position of the first driver, we can ensure that the empty spot is the virtual spot. Therefore, the number of arrays $\left(b_{2}, \cdots, b_{n}\right)$ is the same as the number of arrays $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ that satisfy the conditions, which is $(n+1)^{n-1}$.