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

Input	Output
6 7 4 1 2 2 3 2 4 2 5 3 6 5 6 6 4 1 2 6 4	4 2

Input	Output
4 4 4 1 2 1 3 3 2 2 4 1 2 4 3	-1

Input	Output
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