魔法手镯问题

题目描述

金妮的生日快到了。哈利·波特正在为他的新女友准备生日礼物。礼物是一个由 $n$ 颗魔法珠子组成的魔法手镯。有 $m$ 种不同的魔法珠子。每种珠子都有其独特的特性。将许多珠子串在一起，制作一个美丽的圆形魔法手链。正如哈利波特的朋友赫敏所指出的那样，某些种类的珠子会相互作用并爆炸，哈利波特必须非常小心，确保这些对的珠子不会彼此相邻地串在一起。

有无数种的珠子。如果忽略了围绕手镯中心旋转产生的重复，Harry 可以制作多少种不同的手镯？以 modulo $9973$ 求答案。

输入格式

输入的第一行包含测试用例的数量。

每个测试用例都以一行开头，其中包含三个整数：

• $n$ （$1 ≤ n ≤ 10^9$，且 $\gcd(n, 9973) = 1$）
• $m$ （$1 ≤ m ≤ 10$）
• $k$ （$1 ≤ k ≤ \frac{m(m-1)}{2}$）

接下来的 $k$ 行分别包含两个整数 $a$ 和 $b$ （$1 ≤ a, b ≤ m$），表示 $a$ 类的珠子不能串到 $b$ 类的珠子上。

输出格式

在单独的行中输出每个测试用例的答案。

样例输入

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

题目来源

POJ 月刊--2006.07.30，翠姗香