A group of f friends get together to have a coding problem-solving party at their university computer lab every weekend. Unfortunately, it closes at 22:00, at which point they have no other option but to walk home. The city they live in can be described as n junctions connected by m bidirectional roads. Since these friends have been interrupted from coding their solutions, each one of them wants to get home as fast as possible to finish his and submit it. At the same time, they each have a few problems that they want to discuss with the others, so they will pick such a path that the entire group can walk together for as long as possible. On top of that, so that this walk would feel fresh every time, they would like to take a different path each weekend, for as long as possible. 

The group of friends were able to figure out both the length of the longest path they could all efficiently walk together, as well as how many distinct such paths there are - do you think you can do it, too?

Input

The first line contains an integer T - the number of test cases. T test cases follow, each in the given format. Test cases are separated by a blank line.

The first line of a case contains four integers n m c f - the number of junctions, the number of two-way roads connecting the junctions, the junction at which the computer lab is located, and the number of friends. Junctions are numbered from 1 to n.

The second line contains f distinct integers F₁  ... F_f - F_i is the junction where friend number i lives. None of them are equal to c.

The following m lines contain three integers x y z, denoting a two-way road connecting junctions x and y, of length z. Each unordered pair x, y will be present at most once.

You can assume that the city is connected.

Output

Output two integers L and W.

A 'path' is a sequence of junctions a₁ ... a_kwhere for all 1 ≤ i < k the junctions a_i and a_i+1 are connected by a road.

L is the length of the longest path, such that for all 1 ≤ i ≤ f if after walking this path friend number i can get home the soonest at some time L+t_i, there exists no path from c to F_i shorter than L+t_i. In other words, none of the friends could have gotten home sooner if they would have chosen a different path which did not include the one of length L.

W is the number of such paths, modulo 10⁹+7.

Two paths are considered distinct if either

a) they contain a different number of junctions

or

b) they contain the same number of junctions (lets call that k), where one path is described by a₁ ... a_k and the other by b₁ ... b_k, and there exists some 1 ≤ i ≤ k such that a_i ≠ b_i.

Constraints

1  ≤ f < n ≤ 5000

n-1 ≤ m ≤ min(10⁶, n*(n-1)/2 )

1 ≤ c ≤ n

1 ≤ F_i ≤ n

1 ≤ x < y ≤ n

1 ≤ z ≤ 4*10⁵ 

1 ≤ T ≤ 500

Additionally, if T > 1, n ≤ 50.

The largest input file is under 16MB.

Example

Input:
3
9 12 2 3
9 8 1
2 5 3
2 3 7
2 4 5
3 6 4
6 7 2
5 7 20
4 7 8
4 8 50
7 9 10
7 8 30
1 8 15
1 9 15

9 12 2 3
9 8 1
2 5 3
2 3 7
2 4 5
3 6 4
6 7 2
5 7 20
4 7 8
4 8 10
7 9 10
7 8 30
1 8 15
1 9 15

9 12 2 3
9 8 1
2 5 3
2 3 7
2 4 5
3 6 4
6 7 2
5 7 20
4 7 8
4 8 10
7 9 10
7 8 30
1 8 4
1 9 4

Output:
13 2
5 1
15 1

Explanation

In the first case, the paths are 2,3,6,7 and 2,4,7. Friends number 1 and 2 can then go straight home, and friend number 3 can go home either through junction 8 or 9. For each friend, this is an optimal path.

In the second case, friend number 1 can get home the fastest the same ways as before, friend number 2 can get home fastest by going 2,4,8 and friend number 3 by going 2,4,8,1. Hence the longest path which all friends are willing to take is 2,4 of length 5, and no other such path exists.

In the third case, the first friend can get home the fastest by 2,3,6,7,9 or 2,4,7,9 or 2,4,8,1,9; the second friend's only fastest path is 2,4,8, and the third friend is only willing to take the path 2,4,8,1. Hence the longest path they are all willing to take has length 15 and it is 2,4,8.