Ami Dongsuo 是藏语中对山神的称呼，它守护着祁连山脉，其汉名为牛心山。Ami Dongsuo 是一座神山，因关于卓尔山的奇妙爱情故事而闻名。周围的环境使得 Ami Dongsuo 形成了一个巨大的牧羊场。

根据生态学家马先生的一份令人震惊的新报告，Ami Dongsuo 总共有 $n$ 个不同的牧场。在当地牧民的帮助下，马先生描述了每个牧场的羊的数量以及所有牧场之间的路径。

今天，在马先生的带领下，三位探险家 Alice、Bob 和 Carol 决定参观 Ami Dongsuo 的一些牧场。马先生向他们提出了一个要求，该要求由一个整数 $k$ 描述，他们需要满足该要求。这三位探险家将从同一个牧场出发，并选择三条不同的路线，起点由他们自己选择，因此可以是任何地方。此外，一条路线可能经过一个或多个牧场。由于山峰海拔接近 5000 米，上山或攀登是一项非常累人的工作，探险家们达成了一项协议，即路线中所有牧场的海拔高度在访问顺序上应严格递减。如果沿着各自的路线行进，他们最终会到达某些牧场，这些牧场可能不尽相同。马先生提出的要求 $k$ 是，这三个目的地牧场中的羊的总数（考虑重数）等于 $k$。

现在，马先生希望有人能告诉他，对于任何正整数 $k$，Alice、Bob 和 Carol 有多少种不同的方案可以满足他的要求。在这个问题中，我们将一个方案视为一个包含三条不同路线的集合，这些路线共享同一个起点。如果两条路线的起点不同，或者它们访问路径的顺序不同，则认为这两条路线是不同的。如果一个方案中包含的路线至少有一条在另一个方案中不存在，则认为这两个方案是不同的。

输入格式

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

对于每个测试用例，第一行包含三个整数 $n, m$ 和 $w$，分别表示牧场的数量、牧场之间的路径数量以及牧场中羊数量的上限，其中 $1 \le n \le 10000$，$1 \le m \le 30000$，$1 \le w \le 400$。

下一行包含 $n$ 个正整数，其中第 $i$ 个数表示 Ami Dongsuo 中第 $i$ 个牧场的羊的数量，每个数字最大为 $w$。

接下来的 $m$ 行描述了这些牧场之间的所有路径，每行包含两个整数 $u$ 和 $v$，表示第 $u$ 个牧场和第 $v$ 个牧场之间的一条路径，其中 $1 \le u, v \le n$，$u \neq v$，并且我们保证第 $u$ 个牧场的海拔严格高于第 $v$ 个牧场，且任意两个牧场之间最多只有一条路径。

虽然输入没有给出所有牧场的具体海拔，但我们保证它们确实存在，并且测试用例中给出的所有路径都不会产生歧义。此外，对于任何一对牧场，探险家可能无法从海拔较高的牧场前往海拔较低的牧场，因为路线中涉及的牧场海拔受到限制。即使某些路径是从较低海拔通向较高海拔，该路线也可能是不被允许的。

输出格式

对于每个测试用例，输出一行，包含 “Case #x:”（不含引号）以及随后的 $3w$ 个整数，其中 $x$ 是从 1 开始的测试用例编号，随后的第 $i$ 个整数表示对于 $k = i \pmod{10^9+7}$ 时上述不同方案的数量。为了分隔这些不同 $k$ 值的方案数，请在每个数字前插入一个空格。

样例

输入 1

2
4 3 4
1 2 3 4
1 2
1 3
1 4
4 6 4
1 2 3 4
1 2
1 3
1 4
2 3
2 4
3 4

输出 1

Case #1: 0 0 0 0 0 1 1 1 1 0 0 0
Case #2: 0 0 0 0 0 2 5 9 16 11 13 4

说明

在第一个样例中，所有可能方案的起点都是同一个牧场（即第一个牧场），从第一个牧场出发的不同路线有 1, 1 $\to$ 2, 1 $\to$ 3 和 1 $\to$ 4。