How Many Shortest Paths?

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.

Samples

6 7 4
1 2
2 3
2 4
2 5
3 6
5 6
6 4
1 2 6 4

4 2

4 4 4
1 2
1 3
3 2
2 4
1 2 4 3

-1

8 9 4
1 2
1 3
2 4
3 4
4 5
5 6
5 7
6 8
7 8
1 4 5 8

5 4