You are given a $Directed$$Acyclic$$Graph$ consists of $N$ nodes and $M$ edges.

A little bug is currently at node $a_1$ and wants to reach node $a_x$ with the shortest possible path. He must visit nodes $a_1$, $a_2$, . . . . . . , $a_x$, as the given sequence. For each $i$, he can't visit node $a_i$ before visiting node $a_{i-1}$. He may visit as many nodes as he wants between nodes $a_1$ → $a_2$, node $a_2$ → $a_3$ and so on.

You have to find the shortest possible path from node $a_1$ to $a_x$ while fulfilling the requirements. You are also asked to find the total number of possible shortest path(s). Or report if it is impossible to find such a path.

Input

The first line of input will consist of three integers $N,$$M,$ and $X$$(3 ≤ X ≤ N ≤ M ≤ 5 × 10^5)$.

Each of the next $M$ lines will contain two integers $U$ and $V$$( 1 ≤ U, V ≤ N)$ denoting there is a directed edge from node $U$ to node $V$. There are no multiple edges.

The Next line will contain $X$ distinct space separated integers $a_i$$( 1≤ i ≤ X$ and $1 ≤ a_i ≤ N)$.

Output

There is only one line of output with two space separated integers $A$ and $B$, denoting the length of the shortest possible path if there have any and total number of possible shortest path(s) Modulo$100000110059$. It there is not any path fulfilling the requirements just print $-1$ instead.