给你一个简单的无向图,有 $$$n$$$ 个顶点,$$$n$$$ 是偶数。您将在每个顶点上写一个字母。每个字母应该是拉丁字母表中前 $$$k$$$ 字母之一。
如果图中的路径恰好访问每个顶点一次,则该路径称为哈密顿量。如果一个字符串从左到右和从右到左读取相同,则称为回文字符串。如果图中顶点上的字母在不改变顺序的情况下拼成回文字符串,则该路径被称为回文路径。
长度为 $$$n$$$ 的字符串适合以下情况:
- 每个字母都是前 $$$k$$$ 小写拉丁字母之一;
- 如果将字符串的第 $$$i$$$ 个字母写在图的第 $$$i$$$ 个顶点上,则图中将存在一条回文哈密顿路径。
请注意,路径不一定按 $$$1, 2, \dots, n$$$ 的顺序经过顶点。
计算好字符串的数量。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 12$$$; $$$n$$$ 是偶数; $$$0 \le m \le \frac{n \cdot (n-1)}{2}$$$; $$$1 \le k \le 12$$$) —图中的顶点、图中的边数以及可以使用的拉丁字母表的第一个字母的数量。
接下来的 $$$m$$$ 行包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$) - 图形的边缘。该图不包含多条边和自环。
输出
打印一个整数——好字符串的数量。
示例
输入 #1
4 3 3 1 2 2 3 3 4
输出 #1
9
输入 #2
4 6 3 1 2 1 3 1 4 2 3 2 4 3 4
输出 #2
21
输入 #3
12 19 12 1 3 2 6 3 6 3 7 4 8 8 5 8 7 9 4 5 9 10 1 10 4 10 6 9 10 11 1 5 11 7 11 12 2 12 5 12 11
输出 #3
456165084