Matrix exponentiation is and it can be optimized to , but it's too slow and may still get TLE.

I used a O(k) solution.

I solved it by Lagrange Interpolation

Let f(n, k) denote the answer then we have the recurrence

Now $f(n, 1) = 2n $ , which is linear, which implies that f(n, 2) must be quadratic, which implies that f(n, 3) must be cubic and so on..

So for fixed k, f(n, k) will be a kth degree polynomial in n, and therefore i precomputed f(n, k) for n, k upto 2000 and then I answered each test case in O(n) using Lagrange Interpolation.

So overall time complexity O(K² + TN)

My solution for reference

It can be done by combinatorics

https://www.codechef.com/viewsolution/20517309