1993 AIME Problem 11

Alfred and Bonnie play a game in which they take turns tossing a fair coin. The winner of a game is the first person to obtain a head. Alfred and Bonnie play this game several times with the stipulation that the loser of a game goes first in the next game. Suppose that Alfred goes first in the first game, and that the probability that he wins the sixth game is m/n\,, where m\, and n\, are relatively prime positive integers. What are the last three digits of m+n\,?

Leading zeroes must be inputted, so if your answer is 34, then input 034

Full credit goes to MAA for authoring these problems. These problems were taken on the AOPS website.