Reconstructing Bitada

Archaeologists Lara Joft and Indiana Krones have discovered the complete map of the ancient city Bitada. Bitada consists of \(n\) houses labelled from \(1\) to \(n\) connected by \(n-1\) bidirectional roads forming a tree (i.e. there is a unique simple path between any two houses). It is known that in modern-day Bajtogród, a capital built on the ruins of Bitada, there are \(m\) buildings (with \(m \ge n\)) labelled from \(1\) to \(m\) and connected by \(m-1\) roads which also form a tree. Moreover, exactly \(n\) out of the \(m\) buildings are built on the ruins of Bitada. Unfortunately, the numbering of Bitada's houses does not correspond directly to the numbering of the buildings. The only clue is that all roads in Bitada have been covered by roads in Bajtogród. In other words, if house \(a\) is assigned to building \(x\) and house \(b\) is assigned to building \(y\), and there is a road between houses \(a\) and \(b\) in Bitada, then there is a road between buildings \(x\) and \(y\) in Bajtogród.

Both trees have the additional property that every node has degree at most 3. A possible Bitada reconstruction is defined as an assignment of every house to a building such that:

1. Each building is assigned at most one house.
2. If there is a road between house \(a\) and house \(b\) in Bitada, then the buildings assigned to \(a\) and \(b\) must be directly connected by a road in Bajtogród.

Given an integer \(k\), your task is to compute the total number of valid reconstructions modulo \(k\).

Note: Since Bitada and Bajtogród are trees, an assignment that satisfies the above conditions is equivalent to finding an injective mapping \(f:\{1,2,\dots,n\}\to\{1,2,\dots,m\}\) such that for every edge \((a,b)\) in Bitada, \((f(a),f(b))\) is an edge in Bajtogród.

inputFormat

The first line contains three integers \(n\), \(m\) and \(k\) where \(1 \le n \le m\) and \(k\) is a positive integer.

The next \(n-1\) lines each contain two integers \(a\) and \(b\) (with \(1 \le a,b \le n\)) describing a bidirectional road connecting houses in Bitada.

The following \(m-1\) lines each contain two integers \(u\) and \(v\) (with \(1 \le u,v \le m\)) describing a bidirectional road connecting buildings in Bajtogród.

It is guaranteed that both sets of edges form trees and that every node in both trees has degree at most 3.

outputFormat

Output a single integer: the total number of valid Bitada reconstructions modulo \(k\).

sample

1 1 100

1