how to solve this Problem.

since n can be of the order 10^18, can it really be solved using just memoization(i don’t think so) ? can this problem be solved using matrix exponentiation, but the recurrence is not linear. Help.

[EDIT]:

I came up with THIS CODE, can anyone point out why it is giving wrong answer ?