Putnam 2013 B5

Let $X = \{1, 2, \dots, n\}$, and let $k \in X$. Show that there are exactly $k \cdot n^{n-1}$ functions $f: X \to X$ such that for every $x \in X$ there is a $j \geq 0$ such that $f^{(j)}(x) \leq k$. [Here $f^{(j)}$ denotes the $j$th iterate of $f$, so that $f^{(0)}(x) = x$ and $f^{(j+1)}(x) = f(f^{(j)}(x))$.]