珀西·杰克逊与厄里斯相遇

题目描述

在一次冒险中，珀西和他的朋友安娜贝丝、格洛弗遇到了厄里斯——混沌与纷争的女神。原来在现代世界中她的力量已经减弱，如今过了这么久，她更喜欢一些比混沌和纷争更温和的东西，比如健康的竞争和游戏较量。

不过这并不意味着朋友们就能轻易跟她谈妥，并弄清她是否知道被偷走的宙斯闪电的下落。作为交换信息，他们必须和她玩她最喜欢的游戏。游戏规则是：玩家轮流投掷一个 $k$ 面的骰子，并记录下每次掷出的数字 $a_i$（从 $1$ 开始编号），直到得到一个长度为 $n$ 的序列（$n$ 是奇数）。

记 $c$ 为序列的中间下标，即 $\frac{n+1}{2}$。只有序列满足以下三个条件时，主角一方才能获胜：

1. 数字 $k$ 恰好出现一次，并且 恰好 在序列的中间位置；形式化地：$a_c = k$，且对所有的 $i \ne c$ 有 $a_i \ne k$；
2. 在中心的同一侧，距离中心两倍距离的两个位置上的数字相同；即对于任意 $d$ 从 $-\left\lfloor\frac{c-1}{2}\right\rfloor$ 到 $-1$ 以及从 $1$ 到 $\left\lfloor\frac{c-1}{2}\right\rfloor$，有 $a_{c+d} = a_{c+2d}$；
3. 厄里斯的 $m$ 个 喜爱数对 $(x_i, y_i)$ 中，每一对在序列中 连续出现 的次数不超过一次。

否则厄里斯获胜。注意，厄里斯的喜爱数对是有序的，即如果她喜欢 $(x_i, y_i)$，不一定喜欢 $(y_i, x_i)$。

珀西想知道如果他们每次掷骰子的结果等概率出现，他们获胜的概率是多少。为此需要计算满足上述条件的长为 $n$、数字范围 $1$ 到 $k$ 的序列总个数。结果可能很大，请输出模 $10^9+7$ 的值。

输入格式

第一行包含三个整数 $n, k, m$ —— 所需掷骰子的次数（序列长度）、骰子面数、厄里斯的喜爱数对个数（$1 \le n \le 53$，$n$ 为奇数，$2 \le k \le 10$，$0 \le m \le 16$）。保证 $(k-1)^{n-1} \le 10^{36}$。

接下来 $m$ 行，每行两个整数 $x_i, y_i$ —— 第 $i$ 个喜爱数对（$1 \le x_i, y_i \le k$）。保证所有数对互不相同。

输出格式

输出一个整数，表示满足所有条件的长为 $n$ 的序列个数。

评分系统

仅当通过该子任务及所需子任务的所有测试时，才能获得该子任务的分数。

在所有子任务中，除了第 8 组，都满足 $(k-1)^{n-1} \le 10^{30}$，并且所有 $m$ 个喜爱数对是等概率生成的。

样例

样例 1

输入

3 6 1
6 6

输出

25

样例 2

输入

5 8 1
1 2

输出

49

样例 3

输入

7 5 2
1 2
2 1

输出

254