时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有一片透明玻璃，我们可以在上面涂色。涂色后，你可以对它做两种操作：

　　1.旋转，顺时针或逆时针旋转 90 度；

　　2.翻转，水平或垂直翻转；

　　不管进行多少次旋转或翻转，我们看到都是相同的图形，我们把这样的图形称为"对称图"。下图是操作示例。请注意，图中并不是对称图。

　　现在给你一块 \(n×n\) 的方格状透明玻璃和 \(k\) 种颜色的油漆。请你给每个方格都涂上颜色，涂完后得到一幅对称。但是这块玻璃上有 \(m\) 个方格事先已被涂上了颜色，你不能修改它们。

　　请问，总共能画出多少种不同的对称图？

【输入格式】

　　第一行，三个空格间隔的整数 \(n,m,k\)。
　　接下来 \(m\) 行，每行两个整数 \(x\) 和 \(y\)，表示坐标为 \((x,y)\) 的格子已被涂上了颜色，注意：坐标为 \(0\sim (n-1)\) 范围的整数。

【输出格式】

　　一行，一个整数，表示方案总数，结果可能很大，请输出 \(Mod\ 100 000 007\) 后的结果。

【输入输出样例1】

　Input

3 0 2

　Output

8

【样例1解释】

　　有下面8种方案：

【输入输出样例2】

　Input

4 2 3
1 1
3 1

　Output

3

【输入输出样例3】

　Input

10 10 8
2 3
7 1
6 0
1 8
9 2
1 1
8 7
3 3
4 1
8 8

　Output

16777216

【数据说明】

　　对于 \(50\%\) 的数据 \(1≤n≤500\)，\(0≤m≤100\)，\(1≤k≤100000\)
　　对于 \(100\%\) 的数据 \(1≤n≤10000\)，\(0≤m≤2000\)，\(1≤k≤100000\)

【来源】

　　Mr.he