In addition fond of programing, Jack also loves painting. He likes to draw many interesting graphics on the paper. One day,Jack found a new interesting graph called Palindrome graph. No matter how many times to flip or rotate 90 degrees, the palindrome graph are always unchanged. Jack took a paper with n*n grid and K kinds of pigments.Some of the grid has been filled with color and can not be modified.Jack want to know:how many ways can he paint a palindrome graph?
输入解释
There are several test cases. For each test case,there are three integer n m k(0<n<=10000,0<=m<=2000,0<k<=1000000), indicate n*n grid and k kinds of pigments. Then follow m lines,for each line,there are 2 integer i,j.indicated that grid(i,j) (0<=i,j<n) has been filled with color. You can suppose that jack have at least one way to paint a palindrome graph.
输出解释
For each case,print a integer in a line,indicate the number of ways jack can paint. The result can be very large, so print the result modulo 100 000 007.