ELMO SL 2014 C5

Let $n$ be a positive integer. For any $k$ , denote by $a_k$ the number of permutations of $\{1,2,\dots,n\}$ with exactly $k$ disjoint cycles. (For example, if $n=3$ then $a_2=3$ since $(1)(23)$ , $(2)(31)$ , $(3)(12)$ are the only such permutations.) Evaluate $$a_n n^n + a_{n-1} n^{n-1} + \dots + a_1 n.$$Proposed by Sammy Luo