US-TST 2010 Problem 8

Let $m,n$ be positive integers with $m \geq n$ , and let $S$ be the set of all $n$ -term sequences of positive integers $(a_1, a_2, \ldots a_n)$ such that $a_1 + a_2 + \cdots + a_n = m$ . Show that $$\sum_S 1^{a_1} 2^{a_2} \cdots n^{a_n} = {n \choose n} n^m - {n \choose n-1} (n-1)^m + \cdots + (-1)^{n-2} {n \choose 2} 2^m + (-1)^{n-1} {n \choose 1}.$$