A soccer team has $22$ available players. A fixed set of $11$ players starts the game, while the other $11$ are available as substitutes. During the game, the coach may make as many as $3$ substitutions, where any one of the $11$ players in the game is replaced by one of the substitutes. No player removed from the game may reenter the game, although a substitute entering the game may be replaced later. No two substitutions can happen at the same time. The players involved and the order of the substitutions matter. Let $n$ be the number of ways the coach can make substitutions during the game ,including the possibility of making no substitutions. Find the remainder when $n$ is divided by $1000$
There are substitutions. The number of ways to sub any number of times must be multiplied by the previous number. This is defined recursively. The case for subs is , and the ways to reorganize after subs is the product of the number of new subs () and the players that can be ejected (). The formula for subs is then with .
Summing from to gives . Notice that . Then, rearrange it into . When taking modulo , the last term goes away. What is left is