3134

3134. 魔法手链

题目

给定 $m$ 种不同颜色的魔法珠子，每种颜色的珠子的个数都足够多。

现在要从中挑选 $n$ 个珠子，串成一个环形魔法手链。

魔法珠子之间存在 $k$ 对排斥关系，互相排斥的两种颜色的珠子不能相邻，否则会发生爆炸。（ 同一种颜色的珠子之间也可能存在排斥）

请问一共可以制作出多少种不同的手链。

注意，如果两个手链经旋转后能够完全重合在一起，对应位置的珠子颜色完全相同，则视为同一种手链。

答案对 $9973$ 取模。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含三个整数 $n,m,k$。

接下来 $k$ 行，每行包含两个整数 $a,b$，表示颜色 $a$ 的珠子不能和颜色 $b$ 的珠子相邻。

$m$ 种颜色编号为 $1 \sim m$。

输出格式

每组数据输出一行一个整数，表示答案。

数据范围

$1 \le T \le 10$,

$1 \le n \le 10^9$,

$gcd(n, 9973) = 1$,

$1 \le m \le 10$,

$0 \le k \le \frac{m(m+1)}{2}$,

$1 \le a,b \le m$

输入样例：

4
3 2 0
3 2 1
1 2
3 2 2
1 1
1 2
3 2 3
1 1
1 2
2 2

输出样例：

4
2
1
0

题解