Solution:

Say $f(f(x)) = a$ for all $x,$ and let $S = \{x : f(x) = a\}.$ Picking any $t \in S,$ we get $a = f(f(t)) = f(a),$ so $a \in S.$ Every $x$ satisfies $f(x) \in S$ (because $f(f(x)) = a$), and if $x \notin S$ then $f(x) \ne a,$ so $f$ maps the complement of $S$ into $S \setminus \{a\}.$ Conversely, any $f$ built this way works.

If $|S| = k,$ we choose the constant $a$ in $7$ ways, the remaining $k - 1$ elements of $S$ in $\binom{6}{k-1}$ ways, and an image in $S \setminus \{a\}$ for each of the $7 - k$ other elements in $(k-1)^{7-k}$ ways. Hence $$N = 7\sum_{k=1}^{7} \binom{6}{k-1}(k-1)^{7-k} = 7\,(0 + 6 + 240 + 540 + 240 + 30 + 1) = 7 \cdot 1057 = 7399.$$

The remainder when $N$ is divided by $1000$ is $399.$