C. О меняющемся дереве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано корневое дерево, состоящее из n вершин, пронумерованных от 1 до n. Корень дерева находится в вершине с номером 1.

Изначально во всех вершинах записано число 0. Далее приходят q запросов, каждый из которых имеет один из следующих двух видов:

  • Формат запроса: 1 v x k. В ответ на запрос нужно к числу, записанному в вершине v, добавить x; к числам, записанным в потомках вершины v на расстоянии 1, добавить x - k; и так далее, к числам, записанным в потомках на расстоянии i, нужно добавить x - (i·k). Расстоянием между двумя вершинами считается длина кратчайшего по количеству ребер пути между этими вершинами.
  • Формат запроса: 2 v. В ответ на запрос требуется вывести, какое число сейчас записано в вершине v по модулю 1000000007 (109 + 7).

Выполните заданные во входных данных запросы.

Входные данные

В первой строке задано целое число n (1 ≤ n ≤ 3·105) — количество вершин в дереве. Во второй строке задано n - 1 целое число p2, p3, ... pn (1 ≤ pi < i), где pi — это номер вершины, являющейся предком вершины i в дереве.

В третьей строке записано целое число q (1 ≤ q ≤ 3·105) — количество запросов. В следующих q строках заданы запросы, по одному на строке. Первое число в строке type означает тип запроса. Если type = 1, то далее заданы целые числа v, x, k (1 ≤ v ≤ n; 0 ≤ x < 109 + 7; 0 ≤ k < 109 + 7) через пробел. Если type = 2, то далее задано целое число v (1 ≤ v ≤ n) — вершина, в которой нужно узнать значение числа.

Выходные данные

Для каждого запроса второго типа на отдельной строке выведите число, записанное в вершине, обозначенной в запросе, по модулю 1000000007 (109 + 7).

Примеры
Входные данные
3
1 1
3
1 1 2 1
2 1
2 2
Выходные данные
2
1
Примечание

О корневом дереве можно прочитать здесь: http://ru.wikipedia.org/wiki/Дерево_(теория_графов).