William writes the number $1$ on a blackboard. Every turn, he erases the number $N$ currently on the blackboard and replaces it with either $4N + 1$ or $8N + 1$ until it exceeds $1000$, after which no more moves are made. If the minimum possible value of the final number on the blackboard is $M$, find the remainder when $M$ is divided by $1000$.

Let's think step by step and output the final answer within \boxed{}.
user