"I'm tired of seeing the same scenery in the world." ---
's world can be simplified as a directed graph with vertices and edges.
A in is an ordered list of vertices for some non-negative integer such that is an edge in for all . A can be empty in this problem.
A in is an ordered list of distinct vertices for some positive integer such that is an edge in for all . All circular shifts of a cycle are considered the same.
satisfies the following property: Every vertex is in at most one cycle.
Given a fixed integer , count the number of pairs modulo such that

1. are paths;
2. For every vertex , v is in or ;
3. Let c(P, v) be the number of occurrences of v in path P. For every vertex v of G, .

The first line contains  integers ,  and  ().
Each of the next  lines contains two integers  and , denoting an edge from vertex  to  (). 
No two edges connect the same pair of vertices in the same direction.

Output one integer --- the number of pairs  modulo .

2 2 1
1 2
2 1

6

2 2 2
1 2
2 1

30

3 3 3
1 2
2 1
1 3

103