UCF is now the nation’s second largest university in student population.  To meet the demands of a growing student body, the university is always constructing new buildings.  One of the issues is the campus needs many new buildings but has limited space. To help make room for new buildings, a new restructuring method is being used!

Each day (until the end of restructuring) a building is selected for “reconstruction”. During reconstruction, all buildings that are connected to the selected building and only to the selected building are combined into (torn down and then added as new parts to) the selected building. Every building has a given cost associated with applying this reconstruction operation; when a building is selected and other buildings are combined with it, the cost associated with the selected building is the cost for combining the selected group of buildings.

For example, in the building layout below, the building with cost 5 is selected in Day 1. The building with cost 1 (crossed out in the picture in Day 1) is the only building connected to the selected building and this building is connected to no other building. These two buildings are combined and the cost of the operation is 5 (the cost of the selected building). In Day 2, the building with cost 4 is selected (hence the cost 4 for combining) and in Day 3, the building with cost 6 is selected. No more buildings can be selected after Day 3 since every building is connected to more than one building. The total cost for this sequence of combinations is  therefore 5+4+6= 15.

Given the building connections and the costs associated with refactoring the buildings, determine the minimum possible number of buildings that will be left when refactoring is complete, the minimum cost of achieving this minimum size and the number of ways to achieve this minimum cost with minimum size. Two ways are considered different if on the i-th day the building being reconstructed is different or the number of days to complete the reconstruction differs. Since the number of ways to reconstruct the university can be quite large, print the result modulo 1,000,000,007.

Input

The first input line contains a positive integer, n, indicating the number of restructurings to perform. Each restructuring will contain multiple lines. The first line contains two integers, b (1 ≤ b ≤ 500) and c (1 ≤ c ≤ 2000), representing (respectively) the number of buildings and the number of connections between them. The next line contains b integers, wi (1 ≤ wi ≤ 500), representing the cost of performing a reconstruction on the i-th selected building. The next c lines each contain two integers, xi and yi (1 ≤ xi ≤ b, 1 ≤ yi ≤ b, xi ≠ yi), representing two identifiers for buildings that connect. There will be at most one direct connection between any two buildings. Also, every pair of buildings will be directly or indirectly connected.

Output

For each restructuring, first output the heading “Case #d: ”, where d is the test case number, starting with 1. Then, print three integers separated by a single space: the minimum number of buildings left, the minimum cost for achieving this configuration, and the number of ways to achieve the minimum cost with minimum size. Follow the format illustrated in Sample Output.

Example

Input:
3
3 2
1 2 3
3 1
3 2
8 7
80 4 3 2 1 90 5 80
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 8
1 5 6 1 1 4 1 9
1 2
2 3
3 4
4 2
3 6
6 7
6 5
6 8

Output:
Case #1: 1 3 1
Case #2: 1 15 28
Case #3: 3 15 3