Cayley-Hamilton recurrence solving

I had a question regarding this post, after trying the contest recently.

How can we calculate the first rows of M^2, M^3\cdots, M^{k-1} in O(k^2)?

//