Bruce plans to visit his beloved grandmother whom he has not seen in ages. The petrol price is high and the roads are dangerous, so he wants to travel the shortest possible distance. He also wants to know how much choice he has for the route, as he wants to visit his grandmother more often and being Bruce, he loves change.
Bruce wants to surprise his grandmother with a box of cookies every time he visits. Bruce does not know how to make real cookies (digital ones are easy, however!), so he will have to go past a cookie store along the way, possibly increasing the length of the shortest distance.
Task
Bruce will start off in his home town, numbered 
~1~, and his grandmother lives in town 
~N~. Given the distance between each pair of towns and the location of the cookie stores, your task is to determine the length of the shortest route and the number of routes having that length. All routes must visit a town with a cookie store. Bruce is only interested in the last six digits of the number of routes, i.e. the remainder after division by 
~1\,000\,000~.
Input Specification
The first line contains a single integer ~N~, representing the number of towns (numbered ~1~ to ~N~). The next ~N~ lines each contain ~N~ space-separated integers. The 
~j^{th}~ integer on the 
~i^{th}~ line, 
~d_{ij}~, is the distance between town 
~i~ and town 
~j~. Following this is a line containing a single integer 
~M~, the number of cookie stores. The last line contains ~M~ space-separated integers, each representing a town 
~t_j~ that has a cookie store.
Output Specification
Output two space-separated integers, the length of the shortest route, followed by the remainder when the number of routes having this length is divided by ~1\,000\,000~.
Constraints
~2 \le N \le 700~- For
~30\%~ of tests, 
~2 \le N \le 10~.
~1 \le t_j, M \le N-1~
~1 \le d_{ij} \le 1\,000~ for all 
~i \ne j~
~d_{ii} = 0~ (i.e. distance from a town to itself is zero)
~d_{ij} = d_{ji}~ (i.e. distance from town ~i~ to town ~j~ is the same as the distance from town ~j~ to town ~i~)
Sample Input
5
0 2 2 1 1
2 0 1 2 1
2 1 0 2 1
1 2 2 0 2
1 1 1 2 0
2
2 4
Sample Output
3 4
Explanation
In the sample input there are 
~5~ towns, with Towns 
~2~ and 
~4~ containing cookie stores. Bruce, who lives in Town ~1~, wants to visit his grandmother in Town ~5~. There are four routes having a distance of 
~3~:
- Bruce goes from Town
~1 \to 2 \to 5~ (purchasing cookies at ~2~)
- Bruce goes from Town
~1 \to 4 \to 1 \to 5~ (purchasing cookies at ~4~)
- Bruce goes from Town
~1 \to 4 \to 5~ (purchasing cookies at ~4~)
- Bruce goes from Town
~1 \to 5 \to 2 \to 5~ (purchasing cookies at ~2~)
Notice that travelling from Town 
~1 \to 5~ directly has a distance of only ~1~. However, Bruce would then arrive at his grandmother's without any cookies!
Comments
If a shortest path traverses two city with a store each, this counts as a single route or two? i.e. is it a route identified also by which particular city we use for the store?
What do we output if it is impossible to satisfy the given conditions?
The input format implies that the graph is complete (therefore connected). Also, the lower bound on
is 1, so there is always at least 1 cookie shop Bruce can visit. Thus, there will always be at least one path from town 1 to town 
that visits a cookie shop.
Wait if
, the upper bound for 
is 
. This may mean that 
can't be 
.
pblpbl -- I just changed the minimum number of towns to be 2. Thank you for your comment!
Can paths visit more than one cookie store?
Yes.