Counting Sheep in Ami Dongsuo

Ami Dongsuo, the god of the hills in Tibetan, guards the Qilian Mountains, whose Chinese name is Niuxin Mountain.
Ami Dongsuo is a holy mountain which is famous for the fantastic love story about Zhuoer Mountain.
The surrounding environments prompt Ami Dongsuo to form a huge sheep farmland.

According to a shocking new report by the excellent ecologist Mr. Ma, Ami Dongsuo has $n$ different pastures in total.
With the help of local herdsmen, Mr. Ma describes the number of sheep in each pasture and all paths between different pastures.

Today, under his leadership, three adventurers Alice, Bob and Carol decide to visit some pastures in Ami Dongsuo.
Mr. Ma has shown them a requirement, which is described by an integer $k$ that they should meet.
These three adventurers will start their tours at the same pasture and visit three different routes, where their starting point is selected by themselves and thus it could be anywhere.
Furthermore, a route may pass through one or more pastures.
Since the altitude rises to nearly $5000$ meters at the peak, and going up the hill or even climbing is quite a tiring job, adventurers have reached an agreement that the altitudes at all pastures in a route should be strictly decreasing in visiting order.
If go along their routes respectively, they will finally arrive at some pastures, which may not be distinct.
The requirement described by $k$ from Mr. Ma requires that the total number of sheep in these three destinations, considering with the multiplicities, is equal to $k$.

Now, Mr. Ma hopes that someone can tell him, for any positive integer $k$, how many different plans exist for Alice, Bob and Carol that would meet what he requires.
In this problem, we consider a plan as a set with three different routes sharing the common starting point.
Two routes are considered different if their starting points vary or their sequences of visited paths in order vary.
Two plans are considered different if at least one route that is contained in one plan but not in the other exists.

The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $5$.

For each test case, the first line contains three integers $n$, $m$ and $w$ indicating the number of pastures, the number of paths between them and an upper bound of the number of sheep at a pasture respectively, where $1 \leq n \leq 10000$, $1 \le m \le 30000$ and $1 \le w \le 400$.

The next line contains $n$ positive integers and the $i$-th of them indicates the number of sheep at the $i$-th pasture in Ami Dongsuo, where each number is up to $w$.

The following $m$ lines describe all paths between these pastures, each of which contains two integers $u$ and $v$ representing a path between the $u$-th pasture and the $v$-th one, where $1 \le u, v \le n$, $u \ne v$, and we guarantee that the altitude at the $u$-th pasture is strictly higher than that at the $v$-th one and there is at most one path between any two pastures.

Though the input does not give the exact altitudes at all pastures, we guarantee that they do exist and all paths given in a test case are not ambivalent.
In addition, for any pair of pastures, an adventurer may not be able to visit a route from the higher one to the lower one since the altitudes at pastures involved in the route are restricted.
Even if some paths passing from a lower altitude to a higher altitude, the route may not be allowed.

For each test case, output a line contains "Case #x:" (without quotes) and $3 w$ following integers, where $x$ is the test case number starting from $1$, and the $i$-th of the following integers indicates the number of different plans mentioned above for $k = i$ modulo $(10^9 + 7)$.
In order to separate these numbers of different plans in the output, insert a space before each of them.

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

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

In the first sample case, the starting points of all possible plans are the same pasture (i. e. the first pasture),
and the different routes starting from the first pasture are 1, 1 -> 2, 1 -> 3 and 1 -> 4.

The 43rd ACM International Collegiate Programming Contest Asia Shenyang Regional Contest