CF607D.Power Tree

Genos and Saitama went shopping for Christmas trees. However, a different type of tree caught their attention, the exalted Power Tree.

A Power Tree starts out as a single root vertex indexed 1. A Power Tree grows through a magical phenomenon known as an update. In an update, a single vertex is added to the tree as a child of some other vertex.

Every vertex in the tree (the root and all the added vertices) has some value v__i associated with it. The power of a vertex is defined as the strength of the multiset composed of the value associated with this vertex (v__i) and the powers of its direct children. The strength of a multiset is defined as the sum of all elements in the multiset multiplied by the number of elements in it. Or in other words for some multiset S:

Saitama knows the updates that will be performed on the tree, so he decided to test Genos by asking him queries about the tree during its growth cycle.

An update is of the form 1 p v, and adds a new vertex with value v as a child of vertex p.

A query is of the form 2 u, and asks for the power of vertex u.

Please help Genos respond to these queries modulo 109 + 7.

Genos 和 Saitama 去购买圣诞树。然而，一种不同类型的树引起了他们的注意——尊贵的“幂树”（Power Tree）。

一棵幂树最初仅包含一个编号为 1 的根顶点。幂树通过一种被称为“更新”（update）的神奇现象生长：每次更新中，恰好向树中添加一个新顶点，作为某个已有顶点的子节点。

树中的每个顶点（包括根顶点以及所有后续添加的顶点）都关联有一个值 $v_i$。一个顶点的幂（power）被定义为：由该顶点自身的值 $v_i$ 及其直接子节点的幂所构成的多重集（multiset）的强度（strength）。而一个多重集的强度定义为：该多重集中所有元素之和乘以该多重集的元素个数。换言之，对任意多重集 $S$，有：

Saitama 已经知晓树将经历的所有更新操作，因此他决定在树的生长过程中向 Genos 提出若干查询，以此测试 Genos 的能力。

一次更新形如 1 p v，表示向顶点 $p$ 添加一个值为 $v$ 的新子顶点。

一次查询形如 2 u，表示询问顶点 $u$ 的幂。

请帮助 Genos 回答这些查询，结果对 $10^9 + 7$ 取模。

The first line of the input contains two space separated integers _v_1 and q (1 ≤ _v_1 < 109, 1 ≤ q ≤ 200 000) — the value of vertex 1 and the total number of updates and queries respectively.

The next q lines contain the updates and queries. Each of them has one of the following forms:

• 1 p__i v__i, if these line describes an update. The index of the added vertex is equal to the smallest positive integer not yet used as an index in the tree. It is guaranteed that p__i is some already existing vertex and 1 ≤ v__i < 109.
• 2 u__i, if these line describes a query. It is guaranteed u__i will exist in the tree.

It is guaranteed that the input will contain at least one query.

输入的第一行包含两个以空格分隔的整数 $v_1$ 和 $q$（$1 \leq v_1 < 10^9$，$1 \leq q \leq 200\,000$），分别表示顶点 1 的权值，以及更新与查询操作的总次数。

接下来的 $q$ 行描述了这些更新与查询操作。每行具有以下两种形式之一：

• 1 p_i v_i：表示一次更新操作。新增顶点的编号为尚未在树中使用的最小正整数。保证 $p_i$ 是树中已存在的某个顶点，且 $1 \leq v_i < 10^9$。
• 2 u_i：表示一次查询操作。保证 $u_i$ 在树中存在。

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

For each query, print out the power of the given vertex modulo 109 + 7.

对于每个查询，输出给定顶点的幂对 $10^9 + 7$ 取模的结果。

For the first sample case, after all the updates the graph will have vertices labelled in the following manner: 1 — 2 — 3 — 4 — 5

These vertices will have corresponding values: 2 — 3 — 5 — 7 — 11

And corresponding powers: 344 — 170 — 82 — 36 — 11

对于第一个样例，所有更新操作完成后，图中的顶点标签如下所示：1 — 2 — 3 — 4 — 5

这些顶点对应的值分别为：2 — 3 — 5 — 7 — 11

对应的幂次分别为：344 — 170 — 82 — 36 — 11