给定一棵具有 $n$ 个顶点的树 $\mathcal{T}$，顶点编号为从 $1$ 到 $n$ 的连续自然数。利用这棵树，我们将创建一个无向的、初始为空的图 $\mathcal{G}$。需要执行两种类型的操作：

• $+ \ v \ w$ ($1 \le v \le w \le n$) —— 向图 $\mathcal{G}$ 中添加一个顶点，该顶点标记为一对数字 $(v, w)$。
• $- \ v \ w$ ($1 \le v \le w \le n$) —— 从图 $\mathcal{G}$ 中移除一个标记为 $(v, w)$ 的顶点。

图 $\mathcal{G}$ 的顶点上所写的数字对对应于给定树 $\mathcal{T}$ 中的路径——这两个数字表示该路径两个端点的索引，如果路径仅由单个顶点组成，则这两个数字可以相等。

在任何时刻，如果图 $\mathcal{G}$ 中两个顶点对应的 $\mathcal{T}$ 中的路径至少有一个公共顶点，则它们在图 $\mathcal{G}$ 中通过一条边相连。在向图 $\mathcal{G}$ 添加新顶点后，会根据此规则连接边；当移除一个顶点时，所有与该顶点关联的边也会被移除。

你的任务是在每次操作后，输出图 $\mathcal{G}$ 中形成团的非空顶点子集的数量。团是指一个子图，其中每一对顶点都通过一条边相连。由于这个数字可能非常大，只需输出其除以 $10^9 + 7$ 后的余数。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 200\,000$)，表示树 $\mathcal{T}$ 的顶点数。

接下来的 $n - 1$ 行，每行包含两个整数。第 $i$ 行的数字为 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n$)，表示树 $\mathcal{T}$ 中存在一条连接顶点 $a_i$ 和 $b_i$ 的边。 保证给定的边描述了一棵合法的树。

下一行包含一个整数 $q$ ($1 \le q \le 50\,000$)，表示对图 $\mathcal{G}$ 的修改次数。

接下来的 $q$ 行，每行属于以下两种类型之一：

• $+ \ v \ w$ ($1 \le v \le w \le n$) —— 向图 $\mathcal{G}$ 中添加一个对应于树 $\mathcal{T}$ 中顶点 $v$ 和 $w$ 之间路径的顶点。
• $- \ v \ w$ ($1 \le v \le w \le n$) —— 从图 $\mathcal{G}$ 中移除一个对应于树 $\mathcal{T}$ 中顶点 $v$ 和 $w$ 之间路径的顶点。

图 $\mathcal{G}$ 中的多个顶点可以具有相同的数字对。保证在指令要求移除具有特定数字对的顶点时，图 $\mathcal{G}$ 中至少存在一个这样的顶点。执行移除操作时，即使当前存在多个对应的顶点，也仅移除其中一个。

输出格式

输出应包含 $q$ 行——第 $i$ 行应包含一个整数，表示第 $i$ 次修改后图 $\mathcal{G}$ 中形成团的非空顶点子集的数量。该数字应以除以 $10^9 + 7$ 后的余数形式给出。

样例

输入 1

5
1 2
5 1
2 3
4 2
6
+ 4 5
+ 2 2
+ 1 3
- 2 2
+ 2 3
+ 4 4

输出 1

1
3
7
3
7
9

说明

样例测试中的树 $\mathcal{T}$ 结构如下：

以下图形展示了连续修改后的图 $\mathcal{G}$。

第一次修改后的图 $\mathcal{G}$：

第二次修改后的图 $\mathcal{G}$：

图 $\mathcal{G}$ 中的两个顶点通过边相连，因为这两个路径在 $\mathcal{T}$ 中的公共顶点是顶点 $2$。

第三次修改后的图 $\mathcal{G}$：

第四次修改后的图 $\mathcal{G}$：

第五次修改后的图 $\mathcal{G}$：

最后一次修改后的图 $\mathcal{G}$：