题目描述

在经历了一轮又一轮的罢工以及城市公共交通停摆之后，Olympovo 市政府决定在节日前完成一次彻底的交通重组。 这项艰巨的任务再次交给了 Deni。

Olympovo 的道路网络由 $N$ 个站点组成，编号为 $1$ 到 $N$。 它们之间共有 $N-1$ 条有向街道，并满足：从站点 $1$ 可以到达所有其他站点。

可以证明，这样的道路网络具有如下性质：

• 若沿着街道从某个站点能够到达另一个站点（途中可以经过其他站点），
• 那么这条路径是唯一的。

交通重组的目标是：从议员们提出的若干条公交线路方案中选出一些，使得每个站点都至少被一条选中的线路经过。

总共有 $K$ 个候选方案。 每条线路都是两个站点之间的一条路径：从第一个站点出发，沿街道前进，到达第二个站点（途中可以经过其他站点）。

Deni 想向议员们证明，他们提出的方案实在太多了。 因此她希望统计：

• 有多少种方法可以从这 $K$ 条候选线路中选出若干条（也可以全部选上），
• 使得每个站点都至少被一条被选中的线路经过。

请编写程序 transport，根据给定的道路网络和线路方案，求出满足条件的选法数量。 由于答案可能很大，只需要输出它对 $10^9+7$ 取模后的结果。

输入格式

第一行一个整数 $N$，表示站点数。

接下来 $N-1$ 行，每行两个整数 $x_i, y_i$，表示一条从站点 $x_i$ 指向站点 $y_i$ 的有向街道。

接下来一行一个整数 $K$，表示候选公交线路的数量。

最后 $K$ 行，每行两个整数 $s_j, e_j$，表示一条候选线路，从站点 $s_j$ 出发，到达站点 $e_j$。

保证对于每条候选线路，都存在且仅存在一条从 $s_j$ 到 $e_j$ 的有向路径。 允许出现完全相同的候选线路（即方案可重复）。

输出格式

输出一个整数，表示满足“每个站点都至少被一条选中线路经过”的选法数量，对 $10^9+7$ 取模。

数据范围

• $1 \le N \le 5000$
• $1 \le K \le 200000$

子任务

只有在通过该子任务及其所有依赖子任务的全部测试点时，才能获得该子任务的分数。

样例 #1

输入 #1

6
1 2
2 3
2 4
1 5
5 6
6
1 3
1 4
5 6
1 5
1 5
2 3

输出 #1

12

说明

Olympovo 的道路网络如下：

• $1 \to 2$
• $2 \to 3$
• $2 \to 4$
• $1 \to 5$
• $5 \to 6$

6 条候选线路分别经过如下站点：

1. $1 \to 2 \to 3$
2. $1 \to 2 \to 4$
3. $5 \to 6$
4. $1 \to 5$
5. $1 \to 5$
6. $2 \to 3$

共有 12 种可行选法，使得每个站点都至少被一条被选中的线路经过：

• I, II, III
• I, II, III, IV
• I, II, III, V
• I, II, III, VI
• I, II, III, IV, V
• I, II, III, IV, VI
• I, II, III, V, VI
• I, II, III, IV, V, VI
• II, III, VI
• II, III, IV, VI
• II, III, V, VI
• II, III, IV, V, VI