A vertex-colored rectangle is a rectangle whose four vertices are all painted with colors. For a vertex-colored rectangle, it's harmonious if and only if we can find two adjacent vertices with the same color, while the other two vertices also have the same color with each other. For example, [1010]begin{bmatrix} 1 & 0\ 1 & 0 end{bmatrix}[1100], [0011]begin{bmatrix} 0 & 0\ 1 & 1 end{bmatrix}[0101] and [1111]begin{bmatrix} 1 & 1\ 1 & 1 end{bmatrix}[1111] are harmonious, while [1001]begin{bmatrix} 1 & 0\ 0 & 1 end{bmatrix}[1001] is not . For each point in {(x,y)∣1≤x≤n,1≤y≤m,x,y∈Z}{(x,y) | 1 le x le n, 1 le y le m, x,y in mathbb{Z}}{(x,y)∣1≤x≤n,1≤y≤m,x,y∈Z}, where Zmathbb{Z}Z is the set of all integers, Kotori wants to paint it into one of the three colors: red, blue, yellow. She wonders the number of different ways to color them so that there exists at least one harmonious rectangle formed by the points, whose edges are all parallel to the xxx- or yyy-axis. That is to say, there exists 1≤x1
A vertex-colored rectangle is a rectangle whose four vertices are all painted with colors. For a vertex-colored rectangle, it's harmonious if and only if we can find two adjacent vertices with the same color, while the other two vertices also have the same color with each other. For example, [1010]begin{bmatrix} 1 & 0\ 1 & 0 end{bmatrix}[1100], [0011]begin{bmatrix} 0 & 0\ 1 & 1 end{bmatrix}[0101] and [1111]begin{bmatrix} 1 & 1\ 1 & 1 end{bmatrix}[1111] are harmonious, while [1001]begin{bmatrix} 1 & 0\ 0 & 1 end{bmatrix}[1001] is not (same number for same color, and different numbers for different colors). For each point in {(x,y)∣1≤x≤n,1≤y≤m,x,y∈Z}{(x,y) | 1 le x le n, 1 le y le m, x,y in mathbb{Z}}{(x,y)∣1≤x≤n,1≤y≤m,x,y∈Z}, where Zmathbb{Z}Z is the set of all integers, Kotori wants to paint it into one of the three colors: red, blue, yellow. She wonders the number of different ways to color them so that there exists at least one harmonious rectangle formed by the points, whose edges are all parallel to the xxx- or yyy-axis. That is to say, there exists 1≤x1
