Logarithmic solution for linear recursive equation

This is a solution for the problem “The Great Wall of Byteland” BWALL Problem - CodeChef 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.