Let $A = \{1, 2, 3, 4, 5, 6, 7\}$, and let $N$ be the number of functions $f$ from set $A$ to set $A$ such that $f(f(x))$ is a constant function. Let $A = \{1, 2, 3, 4, 5, 6, 7\}$, and let $N$ be the number of functions $f$ from set $A$ to set $A$ such that $f(f(x))$ is a constant function. Find the remainder when $N$ is divided by $1000$.
Help Needed:
I am trying to understand this solution.
Define the three layers as domain $x$, codomain $f(x)$, and codomain $f(f(x))$. Each one of them is contained in the set $A$. We know that $f(f(x))$ is a constant function, or in other words, can only take on one value. So, we can start off by choosing that value $c$ in $7$ ways. So now, we choose the values that can be $f(x)$ for all those values should satisfy $f(f(x))=c$. Let's $S$ be that set of values. First things first, we must have $5$ to be part of $S$, for the $S$ is part of the domain of $x$. Since the values in $i\in S$ all satisfy $f(i) = 5$, we have $5$ to be a value that $f(x)$ can be. Now, for the elements other than $5$:
If we have $k$ elements other than $5$ that can be part of $S$, we will have $\binom{6}{k}$ ways to choose those values. There will also be $k$ ways for each of the elements in $A$ other than $5$ and those in set $S$ (for when function $f$ is applied on those values, we already know it would be $5$). There are $6-k$ elements in $A$ other than $5$ and those in set $S$. So, there should be $6^{6-k}$ ways to match the domain $x$ to the values of $f(x)$. So, summing up all possible values of $k$ ($[1,6]$), we have
$\sum_{k=1}^6 k^{6-k} = 6\cdot 1 + 15\cdot 16 + 20\cdot 27 + 15\cdot 16 + 6\cdot 5 + 1) = 1057$
Multiplying that by the original $7$ for the choice of $c$, we have $7 \cdot 1057 = 7\boxed{399}.$
I've given two days but still not able to  understand. I tried using smaller set.
Any other way to solve this problem are also welcomed.
This question has been asked here Number of functions $f$ on $\{1,\cdots,7\}$ s.t. $f(f(x))$ is constant too.
 A: Combinatorially speaking, an "endofunction" or a function from S to itself is a set of cycles of rooted trees. This happens because an element a and its successors a, f(f), f(f(a)),... make a sequence that contains a nonperiodic part followed by a cyclic one.
In the problem above, c is not contain in a larger cycle than 1, $f(c) = c$. If the length is 2 and we have (d,c), then f(f(d)) = d. For larger cycles, f(f(c)) does not fall on c.
What we have now is a rooted tree with 7 nodes and depth maximum 2, since all elements are conected with the root c.
To simplify, we can disregard the c layer and we remain with 6 items forming a set of pointed sets, having the species (or class) description as
$Ens(X.Ens(X))$ with the e.g.f $exp(x.exp(x))$.
It remaind to pick up the coefficient of $ { x^6 \over 6! } = 1057$.
A: Let $X$ be a non-empty set and let $f:X\to X$ be a function such that $f(f (x))=c$ for some $c\in X$.
We can describe this situation also by stating that:$$\text{im} f\subseteq f^{-1}\left(\{c\}\right)$$
Here $c=f(x)$ for some $x$ so that $f(c)=f(f(x))=c$.
So $c$ can be recognized as a fixed point of $f$ and evidently it is unique in having this property.
We discern $3$ disjoint and covering subsets of $X$:

*

*$A=\{c\}$

*$B=f^{-1}\left(\{c\}\right)-\{c\}$

*$C=X-f^{-1}\left(\{c\}\right)$
If we construct such function $f$ then it must be kept in mind that elements of $C$ must be mapped to elements of $B$. This forces us to exclude the case where $C\neq\varnothing$ and $B=\varnothing$.
Next to that there are no obstacles. We can just choose the sets $A$ and $B$. Then $C$ is determined and finally for every $x\in C$ we can choose some $y\in B$ for being the element with $f(x)=y$.
Doing this construction for a set that has $n>1$ elements we find:$$n\times\sum_{k=1}^{n-1}\binom{n-1}{k}k^{n-1-k}$$possibilities.
Here the absence of $k=0$ corresponds with leaving out "non-possibility" where $C\neq\varnothing$ and $B=\varnothing$.
