I am trying to solve this problem but the dp solution would take O(n^2*k) in both approches top down and bottom up after some search I knew that the solution would be using matrix exponentialtion but I do not know what would be the transtion matrix for this problem https://atcoder.jp/contests/dp/tasks/dp_r