现有 个集合，第 个集合有 个元素，共 个互不相同的元素（ ），每个元素有一个唯一的所属集合。
对于每轮操作，我们将所有元素随机匹配为 对，对于每对匹配，我们随机挑选一个元素，将其从原本所属的集合中取出，放入与其匹配的元素的所属集合中。请问期望操作多少轮，所有元素将属于一个集合。
输出答案在模 意义下的值。
第一行输入一个整数 () ，表示测试数据的组数。
接下来依次输入每组测试数据，对于每组测试数据：
第 行输入两个整数 ()，表示初始集合的数量以及每轮操作的匹配数。
第 行输入 个整数 ，()，其中 表示第 个集合有 个元素。
保证所有测试数据 。
对于每组数据，输出一行一个整数表示答案在模 意义下的值。
4 2 1 1 1 2 2 2 2 2 2 1 3 3 2 1 1 2
1 3 499122179 499122180
3 6 5 2 1 1 3 1 2 10 100 90 12 18 1 1 24 7 4 37 6 10 200 102 19 25 11 43 97 19 28 11 45
347465837 225202828 437065763
对于样例 ：
