Patterns
Patterns
Little Sergei likes to play games very much. Today, he invented the following game for himself. He has n2
cubes. Each face of each cube is colored in one of the six colors. Note that different faces of a single cube may have the same color. He also has a square board of size n × n. Each cell of this board should contain exactly one cube. For each cube, Sergei selects its position on the board and its face that will be on top. Thus he obtains an n × n color pattern formed by the colors of the top faces of the cubes.
After playing a little, Sergei was interested how many different color patterns he can get using his cubes. Two color patterns are considered different if there is at least one cell in the pattern which is painted differently. Note that you are not allowed to rotate or reflect the pattern. Sergei is a little boy and has limited knowledge of large numbers, so he interested in the answer modulo 109
+ 7.
Input
The first line contains the size n (1 ≤ n ≤ 5) of the board. The next n2
lines contain descriptions of the cubes. Each description is a string of length 6. This string consists only of the following letters: "R" for red color, "G" for green, "B" for blue, "Y" for yellow, "C" for cyan and "M" for magenta. It is easy to see that the order in which sides are given is not important.
Output
Print one integer: the answer for the given problem modulo 109
+ 7.
2 RRRRRR BBBBBB GGGGGG CCYYMM
72
1 YYYYYY
1