Deduce formula for $\sum_{j=0}^m {m \choose j}(-1)^j j^{m+1} $

Feb 2015
United Kingdom
I am working on the following problem:

For each $m$ we have found the values of
$$\sum_{j=0}^m {m \choose j}(-1)^j p(j)$$
for polynomials of degree at most m.
Use a combinatorial story to find the Stirling number
$$m+1 \brace m$$
and deduce a formula for
$$\sum_{j=0}^m {m \choose j}(-1)^j j^{m+1}.$$

In my Combinatorics lectures, we studied a theorem relating to orthogonality for binomial coefficients. This is what the first sentence of the problem relates to.
So, I know that
$$\sum_{j=0}^m {m \choose j}(-1)^j p(j) = \begin{cases}
0 & \text{when $\deg(p)\leq m-1$} \\
(-1)^m m! & \text{when $\deg(p) = m.$}

By calculating the result of $m+1 \brace m$ for various values of $m$ ($2, 3$ and $4$, to be precise), I managed to show that
$${m+1 \brace m} = {m+1 \choose 2}.$$

However, I am unsure how to solve the very last part of the problem (which requires a deduction).
My main thought about it so far is that: this re-arranged version of the formula for $m+1 \brace m$
$$\sum_{j=0}^m {m \choose j}(-1)^j (m-j)^{m+1} = m! {m+1\choose 2}$$
looks very similar to the formula for the orthogonality for binomial coefficients when $\deg(p) = m$
$$\sum_{j=0}^m {m \choose j}(-1)^j j^{m} = (-1)^m m!.$$
I have not yet been able to relate the two, though.

I would greatly appreciate a HINT(S) as to how to solve this last part of the problem.