How to find the $n^{th}$ power of $M\in\mathbb{R}^{m\times m}$, for $M$ symmetric, $m\le 1000$, and $n$ arbitrary?

Question

I have to find the $n^{th}$ power of matrix $M$ which is symmetric about the main diagonal and all elements on the main diagonal are zero. For example: $$M=\left( \begin{array}{cc} 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 \end{array} \right)$$

Here's what I've done so far:

1. I implemented matrix multiplication which have time complexity $O(m^3)$ and used fast exponentiation to find power of matrix in $O(\log(n))$ iterations of matrix multiplication. This has overall time complexity $O(m^3\log(n))$, which is very slow even for $m=1000$.
2. I find out about $n^{th}$ power of matrix on this website, which is related to eigenvalues and eigenvectors and Jordan normal form.

Now I don't know if $M$ as stated can be converted into Jordan normal form, and if so then how to find eigenvalues, eigenvectors, and finally how to use these to find $M^n$?