We define a point cactus as an undirected connected simple graph where each vertex belongs to at most one simple cycle.

A directed graph is called a rooted outward point cactus if, after converting all its edges to undirected edges, it becomes a point cactus, every cycle in the original graph corresponds one-to-one to a simple cycle in the new graph (i.e., they contain the same set of vertices), and all vertices in the graph are reachable from a specific node, which is called its root.

In simpler terms: it is an outward-rooted tree where some nodes have been replaced by cycles (at least, that is how I generated the data).

↑ I heard that cactus problems traditionally require a diagram ↑

You are given a rooted outward point cactus with the root at node $1$, and a set of vertices $S$. If you perform the following operations:

1. Initially $u \leftarrow 1, t \leftarrow 0$.
2. If $u \in S$, terminate.
3. If no nodes in $S$ are reachable from $u$, $u \leftarrow 1$. Otherwise, choose an outgoing edge $(u, v)$ from $u$ with equal probability, $u \leftarrow v$.
4. $t \leftarrow t + 1$.
5. Return to step 2.

The expected value of $t$ upon termination is the weight. Calculate the weight $\pmod p$.

Input

The first line contains three positive integers $n, m, p$. The next $m$ lines each contain two positive integers $u_i, v_i$, representing a directed edge $u_i \to v_i$ in the graph. The next line contains a binary string of length $n$, where the $i$-th character is '0' if the $i$-th node is not in $S$, and '1' if it is in $S$.

Output

A single integer, the value of the weight $\pmod p$.

Examples

Input 1

3 2 998244353
1 2
1 3
001

Output 1

3

Input 2

10 12 999713303
9 4
6 10
7 8
10 2
5 9
2 7
3 1
1 6
1 4
6 3
4 5
8 10
0111101111

Output 2

499856653

Input 3

20 21 920176261
7 3
8 10
19 12
9 18
6 14
10 15
17 8
15 7
2 17
16 20
5 4
18 5
4 13
4 11
1 2
5 16
7 19
14 4
3 9
13 6
20 1
00010100001111000010

Output 3

306725433

Input 4

70 75 906218893
63 68
70 29
49 15
3 53
18 22
35 44
49 55
31 50
7 10
54 11
12 8
68 9
66 1
61 41
43 20
17 66
47 18
37 12
32 49
46 36
2 21
41 6
5 18
23 42
39 7
64 37
67 40
1 17
69 60
51 46
60 70
56 32
6 2
1 5
8 65
30 19
13 35
14 33
19 28
16 38
55 59
42 69
9 51
65 63
22 48
67 56
11 43
21 39
36 25
50 23
29 67
48 47
67 27
58 13
20 64
23 31
44 62
27 54
34 61
1 58
26 16
44 58
1 23
15 56
42 52
57 69
13 4
10 26
38 24
25 34
53 30
40 45
33 57
24 3
28 14
0000000000000000000000000000000000000000000000000000000000100000000000

Output 4

116

Constraints

$2 \le n \le 10^5$, $1 \le u_i, v_i \le n$, $0.9 \times 10^9 < p < 1.05 \times 10^9, p \in \mathbb{P}$. The given graph is guaranteed to be a rooted outward point cactus. $S$ is guaranteed to be non-empty. $p$ is generated uniformly at random within the given range.

Subtasks

• Subtask 1 (14 pts): $n \le 100$
• Subtask 2 (22 pts): $n \le 5000$
• Subtask 3 (33 pts): $m = n - 1$
• Subtask 4 (31 pts): Original constraints