I'm not sure how to approach the following problem. Any help would be appreciated!
An nxn square is divided into n^2 unit squares. Each of the (n+1)^2 vertices is to be colored either red or blue. How many different colorings are there such that each unit square has exactly two red vertices?
Note: Two colorings are considered different if at least one vertex is colored differently in the two schemes.