#P17742. 小A的森林

小A的森林

题目描述

小A通过魔法阵吸收到大量魔力,拥有了强大的实力,于是他准备去探险。

小A来到了一片古老的森林,他发现在这片森林中的很多地方,人们会失去方向感,从而迷失。小A仔细研究了这片森林的灵脉,灵脉是一张无向无环联通图。通过进一步的研究,小A还了解到这片森林的灵脉曾经被施加过迷失诅咒。诅咒是一条被污染的灵脉,森林的灵脉被施加过诅咒后,如果有一个子联通块和被污染的灵脉产生共鸣,这个地方的诅咒就会十分明显,使人迷失。

产生共鸣是指两条灵脉同构。具体来说,如果用一个边集来描绘一个灵脉,那么假设一条灵脉为E1E1,另一条为E2E2。两条灵脉能产生共鸣,当且仅当∣E1∣=∣E2∣|E1|=|E2|且存在一个排列PP,使得∀(u,v)∈E1,(Pu,Pv)∈E2\forall (u,v)\in E1,(P_u,P_v)\in E2。

为了解除诅咒,小A希望了解森林的灵脉中,有多少子联通块会和被污染的灵脉产生共鸣。

因为答案太大了,小A希望你告诉他答案对P取模的结果。

输入格式

从标准输入读入。

第一行一个正整数nn,表示森林灵脉的节点个数。

接下来n−1n-1行,每行两个整数x,yx,y,表示x,yx,y之间有连边。

然后一行一个正整数mm,表示被污染的灵脉的节点个数。

接下来m−1m-1行,每行两个整数x,yx,y,表示x,yx,y之间有连边。

最后一个正整数PP,表示对PP取模。

输出格式

输出到标准输出。

一行一个整数,表示答案对P取模的结果。

样例

样例输入 1

5
1 2
2 3
3 4
4 5
3
1 3
2 3
998244353

样例输出 1

3

样例解释

有3条灵脉会产生共鸣:(1,2,3),(2,3,4),(3,4,5)。

数据范围

1≤n≤2000,1≤m≤121\le n \le 2000,1\le m \le 12

104<P≤109+710^4< P \le 10^9+7

subtask 1 13pts n≤10n\le 10

subtask 2 11pts n≤20n\le 20

subtask 3 19pts 被污染的灵脉树型为一条链。

subtask 4 12pts 被污染的灵脉树型为一个菊花。

subtask 5 17pts n≤500,m≤10n\le 500,m\le10,PP是质数。

subtask 6 9pts n≤1000n\le 1000,PP是质数。

subtask 7 11pts n≤500n\le 500

subtask 8 8pts 无特殊限制。

本次核对PDF:task.pdf,第6–7页。

原题面:task.md。