说明

FQ有n个气球，排成一排，顺次分别标号1到n。FQ要用m种颜色对它们染色，但是不希望有任何两个标号相邻的气球颜色是一样的。

聪明的ZQ马上意识到，FQ一共有m(m-1)^n-1种不同的染色方法。但是ZQ发现有些方案颜色太繁杂，导致美观程度不足，为此ZQ给出了k个标号a₁, a₂, a₃, ..., a_k(1 ≤ a_i ≤ n)，并要求FQ给这k个标号对应的气球染的颜色是一样的。

于是现在FQ还有多少种染色方法？

输入格式

多组测试用例，输入第一行为测试用例数目T(T≤50)。

每组测试样例的第一行是三个用一个空格分开的整数n，m，k。之后一行包含k个用空格分开的整数a₁, a₂, a₃, ..., a_k。

数据保证：(1) 1 ≤ n ≤ 10¹² (2) 1 ≤ m ≤ 10⁵ (3) 0 ≤ k ≤ 2000 (4) a_i ≠ a_j(i ≠ j)

输出格式

对于每组测试用例，输出一行包含一个整数，表示你的结果。由于答案可能很大，请输出结果对1000000007取模的余数。

1
5 2 3
1 3 5

2

提示

现有五个气球，共有两种颜色，1，3，5号气球必须涂相同的颜色。分别用a和b表示两种不同的颜色。那么染色方案数目就是ababa，babab两种。

来源

输入输出练习 洛谷