https://cses.fi/problemset/task/2174
i am clueless for this problem. please help me .
I have solved the easy verison of problem using O(N) dp.
I have spent a good amount of time thinking but could not find any solution.

It would be nice if i get any hints.. instead of actual solution...

I have given thoughts about matrix exponentiation, or any observation patterns ... nothing seems to workout.