Problem 7: Abstract Painting

https://open.kattis.com/problems/abstractpainting

Color square by square, starting at the top-left square.

To color the top-left square, there are $\binom{3}{2} = 3$ways to choose the two colors for the square. Then, there are $\binom{4}{2}=6$ ways to arrange these colors. So, there are $3 \cdot 6 = 18$ways to color the top-left square.

Next, move right and color the rest of the squares in the first row. For these squares, we'll have already colored the square to the left, which means one line is colored already. So, one color is already fixed, and there are then $\binom{2}{1}=2$choices for the second color. Moreover, there are $\binom{3}{2}=3$ways to arrange the remaining three lines of the square. So, there are $2 \cdot 3 = 6$ways to color the squares of the first row. Similarly, there are $6$ways to color the squares of the first column as well.

For the rest of the squares, we can keep coloring squares with two lines already colored, until we have colored the entire painting. For each square with two lines already colored, there are two cases:

• Both lines are the same color: there are $\binom{2}{1}=2$ways to choose the second color, and only $1$way to color the remaining two lines (both must be the other color). So, there are $2 \cdot 1=2$colorings.

• The two lines are different colors: both colors of the square are defined by these two lines. There are $\binom{2}{1}=2$ways to color the remaining two lines. So there are $2 \cdot 1=2$colorings.

Therefore, for these squares, there are always $2$colorings.

So, to count the total number of good paintings, start with 18 for the first square. Multiply by 6 for each other square in the first row or first column, and multiply by 2 for every other square. That gives us the expression:

Remember to take mod 1000000007 after each multiplication step to avoid integer overflow! Also, use long longs.