Think about columns. Specifically, can we consider even and odd columns separately?

The key observation for this problem is that it is necessary and sufficient for columns with the same parity to have the same sum.

Why? Well, consider a ~3 \times 2~ grid:

a b c
d e f

Then:

$$\displaystyle a + b + d + e = b + c + e + f$$

Or:

$$\displaystyle a + d = c + f$$

Once we've realized this, we can iterate through all possible sums ~K~ from ~2~ to ~2M~. For each column, if there are two zeroes, we can either use a formula, or pre-calculate how many ways there are to fill in the two cells. If there are two elements, then we check that they sum to ~K~. If there is one, we check that it is not too large and not too small so that we can fill in the other cell to make the column sum to ~K~.

We need a few optimizations here. Assume we are considering the columns independently. First, instead of iterating from ~2~ to ~2M~, let's make a single pass through the grid, and calculate the minimum possible sum and maximum possible sum.

Then clearly if there are two or one elements in a column, there is only one way to fill that column to obtain any desired sum. If there are no elements filled in, we can use a formula to calculate, given ~K~, the number of combinations.

To come up with this formula, note that ~f(2) = 1~, ~f(2M) = 1~, and ~f(M + 1) = M~. Also, in general if we increase ~K~ our combination count either goes up or down by ~1~. We want a formula that is the minimum of two lines, one of slope ~1~ and the other of slope ~-1~. It may be helpful to simply guess a formula and check if it's right. At any rate, in this case our formula is ~\min(K - 1, 2M + 1 - K)~.

Once we have come up with our minimum sum ~L~ and maximum sum ~R~, we can use our formula and raise it to the power of the number of zeroes, in order to calculate quickly the number of combinations.

If one column has two filled in numbers that sum to, for instance, ~M + 2~, and another column has a single ~1~, then this is impossible, since there is no number we can pair with the ~1~ to get ~M + 2~.

Similarly, if two filled in numbers sum to ~M~ and another column has a single ~M~, this is impossible.

If two columns are both filled completely, we must ensure they have the same sum.

One simple way to consider all these cases is to set ~L = 2, R = 2M~ to start. Then, if we see a column with one filled element, set ~L = \max(L, x + 1)~, ~R = \min(R, x + M)~. If we see a column with two filled elements, set ~L = \max(L, x)~ and ~R = \min(R, x)~.