Solution:

Break the row into maximal single-color runs. If there are $k$ runs, there are exactly $k - 1$ different-color neighbor pairs. Since runs alternate colors and the five green marbles form at most $5$ runs, there are at most $6$ red runs, hence at most $11$ runs and at most $10$ different-color pairs. With $n$ red marbles there are $n + 4$ neighbor pairs in all, and the requirement says half of them are different-color pairs, so $n + 4 \le 20,$ i.e. $n \le 16.$ Thus $m = 16.$

With $16$ reds and $21$ marbles, the count of different-color pairs must be exactly $10,$ so there are exactly $11$ runs: the colors must alternate as red–green–red–$\cdots$–red with $6$ red runs and $5$ single green marbles between them. The arrangements correspond to compositions of $16$ into $6$ positive parts, of which there are $\binom{15}{5} = 3003.$

Hence $N = 3003,$ and the remainder upon division by $1000$ is $3.$