Given a Matrix n*n size Let the matrix is A .. Now i have to find out.. A+A^1+A^2+A^3+.......+A^k(k=10^9).. i only can find out the A^k using matrix exponentiation... how can i find the solution of the above equation..

EXAMPLE:
n=3,k= 2
  1 4 6
A=6 5 2
  1 2 3
output:
208
484
722

problem link:http://lightoj.com/volume_showproblem.php?problem=1142