$3^n.{(2^{n+1} -1)}^{n-1}$ vertical -row , horizontal -column We can color the first row in $3^n$ ways .Now consider the next row see that if any cell $(2,j)$ has the same color as $(1,j)$ then every cell in this row above this cell has fixed it's color. Now for each $j$ the rest of the cells below it must have different colors w.r.t to the left adjacent cell this can be done in $2^{j-1}$. We can take $j = 1,2,\cdots n+1$ where $n+1$ corresponds to the case that none of the cell in this row has the same color as it's adjacent left cell.So in total $\sum_{j=1}^{n+1}2^{j-1} = 2^{n+1}-1$ways to color the second row for each coloring of the first row.Continuing this process till the last row is colored and we get the desired result as $3^n{(2^{n+1}-1)}^{n-1}$