魔法手镯

Time Limit: 1s

Memory Limit: 65535kb

Description

  给定n(n≤10^9)颗珠子和m种颜色,这n颗珠子可以组成一串手镯,每颗珠子可以用m种颜色来填充,如果两种涂色方法通过旋转手镯可以得到,则两种涂色方法等价。现在再给定K组限制,每组限制a、b代表颜色a和颜色b不能涂在相邻的珠子上面。问一共有多少种涂色方法。答案可能很大,你只要输出答案mod 9973的值即可。

Input

  第一行三个整数n,m,k (1 ≤ n ≤ 10^9, gcd(n, 9973) = 1), m (1 ≤ m ≤ 10), k (0 ≤ k ≤ m(m − 1) ⁄ 2),接下来有k行,每行两个整数a和b  (1 ≤ a, b ≤ m),表示颜色a和颜色b不能涂在相邻的珠子上面。

Output

  一行一个整数,表示不同的涂色方案总数mod 9973。

Sample Input

3 2 1
1 2

Sample Output

2

Hint

None

Source

None

提交代码