I was trying this problem from SPOJ: http://www.spoj.com/problems/LVADER/en/. I figured out the recurrence for the problem which is f(x, y) = f(x — 1, y) + f(x, y — 1) + f(x — 1, y — 1), f(x, 0) = f(0, y) = 1. The constraints of the problem does not allow me to use normal DP and I'm not aware how to use matrix exponentiation technique for 2-D recurrence. I read this article: https://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation but I could not fully understand the idea. Any help is really appreciated.