Given a grid with N rows and M columns. This grid contains some vacant spaces represented by 0 and boxes represented by 1. You are initially at cell (1,1) and at any cell, you can move either right or down. While moving right or down, you can push a box in the same direction as you are moving as long as all the boxes in front of you remain in the grid boundaries.

Find the number of ways to go from the cell (1,1) to the cell (N, M). Notes

Multiple boxes can also be pushed as long as all the boxes remain within grid boundaries.

The cells (1,1) and (N. M) can also be occupied by boxes Initially which cannot be pushed in any way.

N=4,M=4 Grid= {0 0 0 1

0 1 1 0

0 1 1 0

0 0 0 0}

Output 5

Any idea how to solve this problem? I though about DP with row wise and column wise sums but how to make state updates.