Problem #4041 - ECNU Online Judge

单点时限: 1.0 sec

内存限制: 256 MB

第 $0$ 年，Cuber QQ 种下了一棵魔树。这是一棵有 $n$ 个结点的有根树，它的根为 $1$ 号结点。

接下来 $m$ 年，每年 Cuber QQ 都会施展魔法来改变这棵树。有两种魔法：

有根树的叶子是指没有孩子的点。注意对于操作完的树，它的叶子集合可能会改变。

现在你知道了 Cuber QQ 每年施展的魔法。你想要预测 $m$ 年以后，魔树会包含多少个点。你只需要求出答案对 $10^{9} + 7$ 取模的结果。

保证 Cuber QQ 不会在根结点为叶子时使用第二种魔法。

第一行两个整数 $n, m$ （ $1 \leq n, m \leq 10^{5}$ ）。

接下来 $n - 1$ 行，每行两个整数 $u, v$ （ $1 \leq u, v \leq n, u \neq v$ ），表示第 $0$ 年魔树中的一条边。

接下来 $m$ 行，第 $i$ 行一个形如 A k（ $1 \leq k < 10^{9} + 7$ ）或 D 的字符串，表示 Cuber QQ 第 $i$ 年进行的操作。

一行一个整数，表示答案。

Input

Output

Input

1 10
A 2
D
A 3
A 4
D
A 5
A 6
A 7
D
A 8

Output

对于样例一，第 $1$ 年加入的点在第 $2$ 年全被删除，第 $3$ 年加入了 $4$ 个点，故最终有 $9$ 个点。

153 人解决，197 人已尝试。

173 份提交通过，共有 826 份提交。

3.3 EMB 奖励。

创建: 4 年，4 月前.

修改: 4 年，3 月前.

最后提交: 2 年，1 月前.

4041. 魔树