巴伊托克考古研究所的首席研究员 Lara Joft 和 Indiana Krones 发现了一张古城 Bitada 的完整地图。这座城市由 $n$ 个房屋组成，编号从 $1$ 到 $n$，并由 $n-1$ 条双向道路连接。任意两个房屋之间都有且仅有一条不重复经过同一条道路的路径。

研究人员知道，巴伊托克（Bajtocja）目前的首都 Bajtogród 建立在 Bitada 的遗址上。Bajtogród 目前有 $m \ge n$ 座摩天大楼，编号从 $1$ 到 $m$，并由 $m-1$ 条街道连接。任意两座摩天大楼之间都有且仅有一条不重复经过同一条街道的路径。已知有 $n$ 座摩天大楼建在 Bitada 的房屋遗址上。遗憾的是，Bitada 的房屋编号与 Bajtogród 的摩天大楼编号并不一定对应。唯一已知的是，Bitada 的所有道路都被 Bajtogród 的街道所覆盖。换句话说，如果房屋 $a$ 的遗址上建有摩天大楼 $x$，房屋 $b$ 的遗址上建有摩天大楼 $y$，且 Bitada 中存在连接房屋 $a$ 和 $b$ 的道路，那么在 Bajtogród 中就存在连接摩天大楼 $x$ 和 $y$ 的街道。

此外，已知在 Bitada 中，每个房屋最多直接与三个其他房屋相连。同样地，在 Bajtogród 中，每座摩天大楼最多直接与三座其他摩天大楼相连。

Bitada 的一种潜在重建方案是指将每个房屋分配给某一座摩天大楼，且满足两个条件：首先，每座摩天大楼最多被分配一个房屋；其次，对于连接房屋 $a$ 和 $b$ 的每一条道路，都存在一条连接分配给房屋 $a$ 的摩天大楼与分配给房屋 $b$ 的摩天大楼的街道。

Lara Joft 和 Indiana Krones 希望分析所有可能的 Bitada 重建方案，并想知道这是否会花费太长时间。为了确定这一点，他们给了你一个正整数 $k$，并询问所有潜在重建方案的数量除以 $k$ 的余数。

输入格式

输入的第一行包含三个整数 $n, m, k$ ($1 \le n \le m \le 3000, 1 \le k \le 10^9$)，分别表示 Bitada 的房屋数量、Bajtogród 的摩天大楼数量以及需要取模的数。接下来的 $n-1$ 行描述了 Bitada 的道路。每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n$)，表示 Bitada 中存在连接房屋 $x$ 和 $y$ 的道路。接下来的 $m-1$ 行描述了 Bajtogród 的街道。每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le m$)，表示 Bajtogród 中存在连接摩天大楼 $x$ 和 $y$ 的街道。你可以假设输入数据满足题目描述中的条件，即任意两个房屋之间有且仅有一条路径，每个房屋最多与三个其他房屋直接相连，任意两座摩天大楼之间有且仅有一条路径，且每座摩天大楼最多与三座其他摩天大楼直接相连。

输出格式

你的程序应输出一行，包含所有潜在重建方案的数量除以 $k$ 的余数。

样例

输入 1

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

输出 1

8

说明

样例解释：潜在的重建方案为 (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$。

子任务