Given a matrix M of size NxN compute efficiently M^k

This is useful to compute PageRank with power method. What is the complexity?

T(K) = T(K/2)+O(multiply)