2011 AIME II Problem 7

Ed has five identical green marbles and a large supply of identical red marbles. He arranges the green marbles and some
of the red marbles in a row and finds that the number of marbles whose right hand
neighbor is the same color as themselves equals the number of marbles whose right hand neighbor is
the other color. An example of such an arrangement is GGRRRGGRG. Let m be the maximum number of
red marbles for which Ed can make such an arrangement, and let N be the number of ways in which
Ed can arrange the m+5 marbles to satisfy the requirement. Find the remainder when N is divided by 1000 .