Consider a square room that has four walls,each made up of wall length * wall height of 1*1 bricks. Given a number of colors of paint, determine the number of possible color patterns that can be created such that no two bricks in the same wall and sharing an edge are the same color. For simplicity,assume that there are no openings in any of the walls. The number of patterns can be quite large so determine the number of patterns modulo 10^9+7.

For example given k=2 colors wall dimension length=1 and height=1 16 different combinations can be created.