We'll start by introducing some notation. Let ~S_{i, j}~ represent the subgrid of ~G~ which spans rows ~1~ to ~i~ and columns ~1~ to ~j~. ~S_{i, j}~ represents an empty grid if ~i = 0~ or ~j = 0~.

Consider the following dp state:

~dp[i][j]~ = the number of ways to fill ~S_{i, j}~

As our base case, if ~i = 0~ or ~j = 0~, then ~S_{i, j}~ is an empty grid and there is only one way to fill it, so ~dp[i][j] = 1~. In all other cases, we have ~1 \leq i, j \leq N~.

Suppose that we are considering the state ~dp[i][j]~. Note that, intuitively, we only care about the prefix ~a_1, ..., a_{i}~ of ~A~ and ~b_1, ..., b_{j}~ of ~B~, since any other elements would never appear in ~S_{i, j}~.

Suppose that the last operation was of type ~1~. The ~1st~ column of ~S_{i, j}~ is fixed, so the number of ways to fill ~S_{i, j}~ would be equal to ~dp[i][j - 1]~. Similarly, if the last operation was of type ~2~, then the ~1st~ row of ~S_{i, j}~ is fixed, so the number of ways to fill ~S_{i, j}~ would be equal to ~dp[i - 1][j]~.

If there were no overlap between the two cases, then we would have ~dp[i][j] = dp[i][j - 1] + dp[i - 1][j]~. We claim that the only time that the overlap does happen, we also have ~a_1 = ... = a_{i} = b_1 = ... = b_{j}~, so we can write ~dp[i][j] = 1~.

Proof of Claim

Suppose that the last operation could be either of type ~1~ or type ~2~ and we would get the same grid for ~S_{i, j}~. Consider the sequence of operations used to create the grid. Suppose that some positive number of type ~1~ operations were performed after a type ~2~ operation. Then the first row of ~S_{i, j}~ would have values ~A_1, ..., A_1, B_1, ..., B_m~ for some ~m~ (possibly ~0~). Equating this sequence elementwise with the sequence ~B_1, ..., B_{j}~ (which we get if the last operation was of type ~2~) gives us ~B_k = A_1~ for all ~1 \leq k \leq j~. We can apply the same logic to get ~A_k = B_1~ for all ~1 \leq k \leq i~, and we are done.

We can optimize this transition by noticing that it is nearly identical to the one used in creating Pascal's triangle, and therefore, we can apply binomial coefficients. The details are left as an exercise for the reader.

Time Complexity: ~O(N)~