Logarithmic solution for linear recursive equation

This is a solution for the problem “The Great Wall of Byteland” http://www.codechef.com/problems/BWALL which is basically solving the linear recursive equation. I have seen normal solution which in involves creation of k^2 transformation matrix and have complexity K^3*log(n) but this looks differnet. Can someone explain how it works and what is its complexity.