Th following question came in a recent on campus test. My understanding is that it requires a dynamic programming approach. However, since I wasn’t able to solve it, I may very well be wrong is this regard.

Here is the question (in simplied words):

Given a matrix of N rows and M columns, find the number of ways to move from top-left to bottom-right corner. You are only allowed to move in the right direction or in the downward direction. Moreover, you cannot take more than two consecutive steps in a particular direction. Since the answer can be large, output it to mod 10^9 + 7.

The constraints were as follows: 1<=N,M<=1000

I have been trying to devise a strategy to solve this but nothing fruitful has yet been achieved. Any help in this regard will be highly appreciated.