Muhammad Ali pulls tiles from bag $3.$ A bag contains three tiles marked $A$, $L$, and $I$. Muhammad wants to pick the letters $ALI$, in that sucession. Randomly, he pulls one til from the bag. If the letter $A$ is drawn, he keeps it. If the letter pulled is other than $A$, he puts it back into the back. He does the same thing with the next tile. If the selected tile is $L$, he keeps it. If it is not $L$, he puts it back in the bag. The probability that Muhammad draws from the bag at most $10$ times can be written in the form $\frac{x_1}{x_2}$, where $x_1$ and $x_2$ are relatively prime numbers. Compute the remainder when $x_1+x_2$ is divided by $1000$. 
$\textbf{Thoughts}$
This seems like an application of casework counting. Here is my best try.
NOTE:Some of these cases could be incorrectly counted.
$3$ draws needed: $1$ case
$4$ draws needed: $2$ cases 
$5$ draws needed: $3$ cases
$6$ draws needed: $4$ cases
$7$ draws needed: $5$ cases
We have an emerging pattern. Therefore, we get $1+2+3+4+5+6+7+9=45$. However, I do not know what my denominator will be...

What is the probability that it takes n draws, imagine the sequence of draws $x_1, x_2, \cdots, x_n$. 
For this this to be a valid draw we have some $x_i=A$ and $x_{n-1}=L$ such that $1 \le i <n-1$. And since it took $n$ draws then $x_n=I$
For a particular $i,j$ the probability is $p_n(i,j)$
$$p_n(i,j)=\left(\frac{2}{3}\right)^{i-1}\left(\frac{1}{3}\right)\left(\frac{1}{2}\right)^{n-i-2}\left(\frac12\right)$$
We need to sum this over all $i$ $$\sum_{i=1}^{n-2}\left(\frac{2}{3}\right)^{i-1}\left(\frac{1}{3}\right)\left(\frac{1}{2}\right)^{n-i-2}\left(\frac12\right)=\frac16\frac{1}{2^{n-2}} \sum_{i=1}^{n-2}\left(\frac{2}{3}\right)^{i-1}2^i=\frac{1}{3.2^{n-1}}.\frac{2\left((\frac{4}{3})^{n-2}-1\right)}{\frac{4}{3}-1} \\\text{Probability that n draws are needed}=p_n=\frac{1}{2^{n-2}}{\left((\frac{4}{3})^{n-2}-1\right)}$$
So probability that he draws at most 10 times $$\sum_{n=3}^{10}p_n=\sum_{n=3}^{10}\left(\left(\frac23\right)^{n-2}-\left(\frac12\right)^{n-2}\right)\\=\frac{(2/3)(1-(2/3)^8)}{(1-2/3)}-\frac{(1/2)(1-(1/2)^8)}{(1-1/2)}\\=\frac{12610}{6561}-\frac{255}{256}$$
Simplifying this we get $$\frac{1555105}{1679616}$$
The final answer $x_1=1555105, x_2=1679616$ and $x_1+x_2=3234721$, therefore that last 3 digits is $721$
