Leading employees of the Byteotian Archaeological Institute, Lara Joft and Indiana Krones, have discovered a complete map of the ancient city of Bitada. The city consisted of $n$ houses numbered from $1$ to $n$ and connected by $n - 1$ bidirectional paths. Between any two houses, there was exactly one path without backtracking.

Researchers know that the current capital of Byteotia, Bajtogród, was built on the ruins of Bitada. Bajtogród currently contains $m \ge n$ skyscrapers numbered from $1$ to $m$ and connected by $m - 1$ streets. Between any two skyscrapers, it is possible to travel without backtracking in exactly one way. It is known that $n$ of the $m$ skyscrapers were built on the ruins of the houses of Bitada. Unfortunately, the numbering of houses in Bitada does not necessarily correspond to the numbering of skyscrapers in Bajtogród. It is only known that all paths of Bitada have been covered by the streets of Bajtogród. In other words, if a skyscraper $x$ was built on the ruins of house $a$, a skyscraper $y$ was built on the ruins of house $b$, and there was a path connecting houses $a$ and $b$ in Bitada, then there is a street connecting skyscrapers $x$ and $y$ in Bajtogród.

Additionally, it is known that in Bitada, each house was directly connected to at most three other houses. Similarly, in Bajtogród, each skyscraper is directly connected to at most three other skyscrapers.

A potential reconstruction of Bitada is an assignment of each house to a certain skyscraper that satisfies two conditions. First, at most one house is assigned to each skyscraper. Second, for every path connecting houses $a$ and $b$, there exists a street connecting the skyscraper to which house $a$ is assigned and the skyscraper to which house $b$ is assigned.

Lara Joft and Indiana Krones would like to analyze all potential reconstructions of Bitada and wonder if it will take them too much time. To find out, they have given you a positive integer $k$ and ask for the remainder of the division of the number of all potential reconstructions by $k$.

Input

The first line of input contains three integers $n, m, k$ ($1 \le n \le m \le 3000$, $1 \le k \le 10^9$), representing the number of houses in Bitada, the number of skyscrapers in Bajtogród, and the modulo $k$ for the result, respectively. The next $n - 1$ lines describe the paths of Bitada. Each contains two integers $x$ and $y$ ($1 \le x, y \le n$) meaning that there was a path connecting houses $x$ and $y$ in Bitada. The next $m - 1$ lines describe the roads of Bajtogród. Each contains two integers $x$ and $y$ ($1 \le x, y \le m$) meaning that there is a street connecting skyscrapers $x$ and $y$ in Bajtogród. You may assume that the input data satisfies the conditions described in the problem statement, i.e., there is exactly one path between any two houses without backtracking, each house is directly connected to at most three others, there is exactly one path between any pair of skyscrapers without backtracking, and each skyscraper is directly connected to at most three others.

Output

Your program should output exactly one line containing the remainder of the division of the number of all potential reconstructions by $k$.

Examples

Input 1

3 5 100
1 2
2 3
1 2
1 3
3 4
3 5

Output 1

8

Note

The potential reconstructions are: (1) $1 \to 2, 2 \to 1, 3 \to 3$, (2) $1 \to 3, 2 \to 1, 3 \to 2$, (3) $1 \to 1, 2 \to 3, 3 \to 4$, (4) $1 \to 1, 2 \to 3, 3 \to 5$, (5) $1 \to 4, 2 \to 3, 3 \to 1$, (6) $1 \to 4, 2 \to 3, 3 \to 5$, (7) $1 \to 5, 2 \to 3, 3 \to 1$, (8) $1 \to 5, 2 \to 3, 3 \to 4$.

Subtasks