SP23880 DCEPC14F - The Toy Store

阿米特打算开一家玩具店，但他意识到需要吸引顾客才能取得成功。于是，他决定为每位顾客免费赠送一套乐高积木。得知这个消息，你也去店里领取了你的免费乐高套装。 你领取的套装中包含了 $N$ 种不同类型的乐高块。这些乐高块的数量是无限的。每种类型的乐高块都有固定的高度。需要注意的是，不同种类的乐高块可能会有相同的高度。 你想知道这套乐高积木的实际价格。这个价格取决于可以用这套积木建造的不同 "美丽建筑" 的数量。 所谓美丽建筑，是指由恰好 $K$ 个乐高块（不必不同种类）组成的建筑，并且这座建筑的总高度对 $M$ 取模后等于 $X$（这些信息可以在积木盒子上找到）。 如果存在某个高度 $H$，使得第一座建筑和第二座建筑在该高度处所用的乐高块不同，那么这两座建筑被视为是不同的。 你需要计算出这份免费样品的实际价格。

输入首先给出一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例包括三行。 - 第一行包含一个整数 $N$，表示不同类型乐高块的数量。 - 第二行包含 $N$ 个整数，用空格分隔。第 $i$ 个整数表示第 $i$ 种乐高块的高度。 - 第三行包含三个整数，分别表示 $M$、$K$ 和 $X$ 的值，用空格隔开。

对于每个测试用例，输出一行，表示该乐高积木套装的价格，并对 $1000000007$ 取模。

- $T \leq 100$ - $1 \leq N \leq 100000$ - $1 \leq M \leq 100$ - $1 \leq K \leq 1000000000$ - $0 \leq X < M$ - 每种乐高块的高度范围为 $1 \leq \text{Height} \leq 1000000000$ **本翻译由 AI 自动生成**