← 返回题目列表

Codeforces · 607/D

D. 电源树

中文机器翻译题面 查看原题

杰诺斯和埼玉去买圣诞树。然而,另一种不同类型的树引起了他们的注意,那就是尊贵的能量树。

能量树从索引为 1 的单个根顶点开始。能量树通过一种称为更新的神奇现象来生长。在更新中,单个顶点作为其他顶点的子节点添加到树中。

树中的每个顶点(根和所有添加的顶点)都有一些与之关联的值 vi。顶点的幂定义为由与该顶点 (vi) 关联的值及其直接子节点的幂组成的多重集的强度。多重集的强度定义为多重集中所有元素的总和乘以其中元素的数量。或者换句话说,对于某些多重集 S:

$$强度(S) = |S| \cdot \sum_{d \in S} d$$

埼玉知道将在树上执行的更新,因此他决定通过向杰诺斯询问有关树在其生长周期期间的问题来测试杰诺斯。

更新的形式为 1 p v,并添加一个值为 v 的新顶点作为顶点 p 的子节点。

查询的形式为 2 u,询问顶点 u 的幂。

请帮助 Genos 响应这些以 109 + 7 为模的查询。

输入

输入的第一行包含两个空格分隔的整数 v1 和 q (1 ≤ v1 < 109, 1 ≤ q ≤ 200 000) — 分别是顶点 1 的值以及更新和查询的总数。

接下来的 q 行包含更新和查询。它们每个都有以下形式之一:

- 1 pi vi,如果这些行描述了更新。添加的顶点的索引等于树中尚未用作索引的最小正整数。保证 pi 是某个已经存在的顶点并且 1 ≤ vi < 109。
- 2 ui,如果这些行描述了一个查询。保证 ui 将存在于树中。

保证输入至少包含一个查询。

输出

对于每个查询,打印出给定顶点模 109 + 7 的幂。

示例

输入 #1

2 5
1 1 3
1 2 5
1 3 7
1 4 11
2 1

输出 #1

344

输入 #2

5 5
1 1 4
1 2 3
2 2
1 2 7
2 1

输出 #2

14
94

注意

对于第一个示例案例,在所有更新之后,图形将具有按以下方式标记的顶点:1 — 2 — 3 — 4 — 5

这些顶点将具有相应的值:2 — 3 — 5 — 7 — 11

及相应权力:344 — 170 — 82 — 36 — 11