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.

3 0 2
4 2 3
1 1
3 1

8
3

FZU

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 105
#define MAXN 100005
#define mod 100000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

ll n,m,k,ans,cnt,flag;
ll x,y,c;
map<ll,int>mp;

ll pow_mod(ll a,ll i,ll nn) // (a^i)%nn
{
    if(i==0) return 1%nn;
    ll temp=pow_mod(a,i>>1,nn);
    temp=temp*temp%nn;
    if(i&1) temp=temp*a%nn;
    return temp ;
}
void change()
{
    ll i,j,t;
    while(!(x<=c&&y<=c))
    {
        t=x;
        x=y;
        y=n+1-t;
    }
    if(x>y) swap(x,y);
}
int main()
{
    ll i,j,t,u,v;
    while(~scanf("%I64d%I64d%I64d",&n,&m,&k))
    {
        c=(n+1)/2;
        u=(1+n/2)*(n/2)/2;
        if(n%2==1) u=u+(n+1)/2;
        mp.clear();
        v=0;
        for(i=1;i<=m;i++)
        {
            scanf("%I64d%I64d",&x,&y);
            x++,y++;
            change();
            t=10000*x+y;
            if(!mp[t]) mp[t]=1,v++;
        }
        ans=pow_mod(k,u-v,mod);
        printf("%I64d\n",ans);
    }
    return 0;
}