P17397 [ICPC 2018 Shenyang R] Counting Sheep in Ami Dongsuo

阿咪东索（Ami Dongsuo），藏语中的山神，守护着祁连山，汉语名为牛心山。阿咪东索是一座神山，因关于卓尔山的美丽爱情故事而闻名。周围的环境促使阿咪东索形成了一片巨大的羊群牧场。 根据杰出的生态学家马先生的一份令人震惊的新报告，阿咪东索总共有 $n$ 片不同的牧场。在当地牧民的帮助下，马先生描述了每片牧场中的羊的数量以及不同牧场之间的所有路径。 今天，在他的带领下，三位冒险者 Alice、Bob 和 Carol 决定游览阿咪东索的一些牧场。马先生向他们展示了一个要求，用一个整数 $k$ 来描述，他们必须满足这个要求。这三位冒险者将从同一片牧场开始他们的旅程，并游览三条不同的路线，出发点是他们自己选择的，因此可以是任何地方。此外，一条路线可能会经过一片或多片牧场。由于山顶的海拔将近 $5000$ 米，上山甚至攀登是一项非常累人的工作，冒险者们达成一致：一条路线上的所有牧场的海拔在游览顺序中必须严格递减。如果沿着各自的路线走下去，他们最终会到达某些牧场，这些牧场可以重复。马先生用 $k$ 描述的要求是：这三个目的地（考虑重复）的羊的总数等于 $k$。 现在，马先生希望有人能告诉他，对于任意正整数 $k$，有多少种不同的计划可供 Alice、Bob 和 Carol 选择并能满足他的要求。在本题中，我们将一个计划视为共享同一个出发点的三条不同路线的集合。如果两条路线的出发点不同，或者它们依次经过的路径序列不同，则认为这两条路线不同。如果存在至少一条路线包含在一个计划中而不在另一个计划中，则认为两个计划不同。

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据的组数，最多为 $5$。 对于每组测试数据，第一行包含三个整数 $n$、$m$ 和 $w$，分别表示牧场的数量、牧场之间路径的数量以及牧场羊的数量上界，满足 $1 \leq n \leq 10000$，$1 \le m \le 30000$，$1 \le w \le 400$。 接下来一行包含 $n$ 个正整数，其中第 $i$ 个数表示阿咪东索中第 $i$ 片牧场的羊的数量，每个数最大为 $w$。 接下来的 $m$ 行描述了这些牧场之间的所有路径，每行包含两个整数 $u$ 和 $v$，表示第 $u$ 片牧场和第 $v$ 片牧场之间的一条路径，满足 $1 \le u, v \le n$，$u \ne v$，并且我们保证第 $u$ 片牧场的海拔严格高于第 $v$ 片牧场的海拔，且任意两片牧场之间至多有一条路径。 尽管输入没有给出所有牧场的精确海拔，但我们保证它们确实存在，且在一个测试数据中给出的所有路径不会产生歧义。此外，对于任意一对牧场，由于路线中涉及的牧场的海拔受限，冒险者可能无法从较高的牧场游览到较低的牧场。即使某些路径允许从低海拔通向高海拔，该路线也可能不被允许。

对于每组测试数据，输出一行包含 “Case #x:”（不含引号）以及接下来的 $3w$ 个整数，其中 $x$ 是测试数据的编号（从 $1$ 开始），接下来的第 $i$ 个整数表示对于 $k = i$ 时，上述不同计划的数量模 $(10^9 + 7)$ 的结果。为了在输出中分隔这些不同计划的数量，在每个数前插入一个空格。

在第一个样例中，所有可行计划的出发点都是同一片牧场（即第一片牧场），从第一片牧场出发的不同路线有 $1$、$1 \to 2$、$1 \to 3$ 和 $1 \to 4$。 翻译由 DeepSeek V4 Pro 完成