Recursion tilingproblem-II

#1

is this tiling problem-II should be solved using recursion or dynamic programming as when i am using recursion i am getting tle

#2

Constraints

1 <= T<= 1000
1 <= N,M <= 100000

as constraints are large and it have overlapping sub-problems so you have to use Dp otherwise it will give TLE