There are $n$ passengers in a line, waiting to board a plane with $n$ seats. For $1 \le k \le n$, the $k^{th}$ passenger in line has a ticket for the $k^{th}$ seat. However, the rst passenger ignores his ticket, and decides to sit in a seat at random. Thereafter, each passenger sits as follows: If his/her assigned is empty, then he/she sits in it. Otherwise, he/she sits in an empty seat at random. How many different ways can all $n$ passengers be seated?