Геос и Сайтама пошли покупать новогодние ёлки, но их внимание привлекло необыкновенное Могучее Дерево. Могучее Дерево изначально состоит из единственной корневой вершины, имеющей номер 1. Могучее дерево иногда растёт благодаря волшебному феномену, известному как обновление. Во время обновления к дереву добавляется один новый лист. Каждой вершине дерева (корню и всем добавленным вершинам) присвоено некоторое значение vi. Мощность вершины определяется как сила мультимножества, составленного из значения данной вершины (то есть числа vi) и значений мощностей её непосредственных детей. Сила мультимножества определяется как сумма всех элементов в мультимножестве, умноженная на их количество, то есть для некоторого мультимножества S:
Сайтама знает, какие обновления произойдут с данным деревом, так что он решил проверить Геноса и задать ему вопросы о мощности разных вершин дерева во время его роста. Каждое обновление имеет вид
1 p v, что означает добавление новой вершины со значением
v, как непосредственного потомка вершины
p. Каждый запрос имеет вид
2 u, что означает, что Генос должен назвать мощность вершины
u в текущий момент. Пожалуйста, помогите Геносу ответить на все вопросы Сайтама. Ответ выводите по модулю
109 + 7.
Примечание
В первом примере после всех обновлений дерево будет выглядеть следующим образом: 1 — 2 — 3 — 4 — 5
Вершинам будут присвоены следующие значения: 2 — 3 — 5 — 7 — 11
Мощности вершин будут, соответственно, равны: 344 — 170 — 82 — 36 — 11