在幼儿园里，站有一排 位小朋友，而老师 Zaoly 手里有 种图案的徽章，每种图案的徽章都有无限多个。Zaoly 会给每位小朋友发放一个徽章。 小朋友们总有一些奇奇怪怪的要求：有的小朋友希望自己的徽章图案，全班只有他一个人能拥有，这样显得自己的徽章稀缺；有的小朋友希望自己的徽章图案，全班大多数人都能拥有，这样方便与其他同学建立联系。为此，Zaoly 发放徽章时必须保证，对于每个整数 （），恰有 位小朋友得到的徽章图案与第 位小朋友的图案相同（这一人数是算上自身的）。 请你帮 Zaoly 算算，他一共有多少种方法发放徽章？如果有小朋友在两种发放方法中得到了不同图案的徽章，则认为这两种发放方法不同。由于答案可能很大，请将答案对 取模。（在此复制：1000000007。） 用数学语言描述就是：对于给出的长度为 的正整数数列 和正整数 ，请你计算有多少个长度为 的整数数列 同时满足以下条件： 对于每个整数 （），都有 。 对于每个整数 （），恰有 个整数 （）满足 。 由于答案可能很大，请将答案对 取模。（在此复制：1000000007。）

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 （）代表数据组数，每组测试数据描述如下：第一行输入用空格隔开的两个整数 和 （；），表示小朋友的数量、徽章图案的数量。第二行输入用空格隔开的 个整数 （），表示恰有 位小朋友得到的徽章图案与第 位小朋友的图案相同（含自身）。除此之外，保证单个测试文件的 值之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示发放徽章的方法数（整数数列的数量），对 取模。