测试数据来自 system/3010

作业已超过截止时间，您无法递交本题目。

对称涂色

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有一个包含若干个方格的透明玻璃片，每个格子都可以涂上颜色。涂色后要求对称，即把玻璃片翻转后看到的图形是相同的。
　　现在给你一片包含 \(n\) 个的方格的透明玻璃和 \(k\) 种颜色的油漆。请你给每个方格都涂上颜色，涂完后得到一幅对称图案。但是这块玻璃上有 \(m\) 个方格事先已被涂上了颜色，你不能修改它们。

　　请问，总共能涂画出多少种不同的对称图？

【输入格式】

　　第一行为整数 \(T\)，表示有 \(T\) 组数据。每组数据包含两行，其中第一行是三个空格间隔的整数 \(n,m,k\)，第二行包含 \(m\) 个行\(0\sim n-1\) 范围的整数，每个整数表示已被涂上了颜色的格子是从左向右数的第几个，保证已经涂色的格子不会破坏对称性，且其中可能有相同的整数。

【输出格式】

　　输出T行，每行一个整数，表示对于输入数据的方案总数，结果可能很大，请输出 \(Mod\ 100 000 007\) 后的结果。

【输入输出样例1】

　Input

3
3 0 2
8 2 3
1 4
10 4 5
2 4 7 8

　Output

4
9
25

【样例解释】

　　对于第1组数据，有下面4种方案：

【数据说明】

　　对于 \(30\%\) 的数据 \(1≤n≤5\)，\(0≤m≤n\)，\(1≤k≤5\)
　　对于 \(100\%\) 的数据 \(T≤50\)，\(1≤n≤10^9\)，\(0≤m≤20000\)且\(m≤n\)，\(1≤k≤100000\)

【来源】

　　Mr.he