STEPNUMS - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

Amazing!!!

Building upong the first paragraph of the editorial i built the solution that is we can caculat A^N using fast exponentiation of matrix so the complexity of this solution is O( 11^3 * logN ) per test case, it should be fast enough for single test case, but it is given that number of test cases are 2 * 10^4 so total time complexity would be O( 2 * 10^4 * 11^3 * logN ) which is damn slow as the time limit is 0.5 second only, anyways i learned this new aspect so see this problem, now i will focus on the following paragraphs to understand the solution,

but this solution is getting wrong ans why? :
I am using memoisation to remove logn factor
https://www.codechef.com/viewsolution/1024746665

without memoisation it is getting TLE which is expected
https://www.codechef.com/viewsolution/1024743101

what is wrong with this solution as i am following the first paragraph correctly