给定 $n$ 个不同的整数序列。所有序列的长度均为 $L$，且序列中的所有整数均在 $1$ 到 $m$ 之间。

你还有一个生成随机数流的机器。初始时，流为空。每一秒，机器都会生成一个 $1$ 到 $m$（包含 $1$ 和 $m$）之间的随机整数，并将其追加到流中。每个随机整数都是独立生成的，且遵循给定的概率分布。

以概率 $1$ 计算，最终每个给定的 $n$ 个序列都会作为流中连续的 $L$ 个元素出现。不同序列的出现位置可能会重叠。在 $n$ 个给定序列中的每一个都至少出现过一次的时刻，机器立即停止。你的任务是计算机器停止时的期望秒数。

输入格式

输入包含一个或多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例的第一行包含三个正整数 $n, m$ 和 $L$：分别表示给定序列的数量、序列中可能出现的整数上限以及每个给定序列的长度（$1 \le n \le 15, 1 \le m \le 100, 1 \le L \le 5 \cdot 10^4$）。

下一行包含 $m$ 个正整数 $a_1, a_2, \dots, a_m$，描述机器生成流所使用的概率分布。机器生成 $1$ 的概率为 $a_1/s$，生成 $2$ 的概率为 $a_2/s$，以此类推，其中 $s = a_1 + a_2 + \dots + a_m$。保证 $s \le 10^9$。

接下来的 $n$ 行，每行包含一个长度为 $L$ 的整数序列。这些序列中的所有整数均为正整数且不超过 $m$。保证所有 $n$ 个给定序列两两不同。

所有测试用例中 $n \cdot L$ 的总和不超过 $777\,777$。

输出格式

对于每个测试用例，将答案计算为不可约分数 $\frac{A}{B}$，并输出整数 $(A \cdot B^{-1}) \pmod{10^9 + 7}$。其中，$B^{-1}$ 是 $B$ 在模 $10^9 + 7$ 下的乘法逆元。

保证对于所有给定的输入，$B$ 与 $10^9 + 7$ 互质。

样例

样例输入 1

1
1 2 2
1 1
1 1

样例输出 1

6