Дано корневое дерево, состоящее из 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).
Выполните заданные во входных данных запросы.
Выходные данные
Для каждого запроса второго типа на отдельной строке выведите число, записанное в вершине, обозначенной в запросе, по модулю 1000000007 (109 + 7).
Примечание
О корневом дереве можно прочитать здесь: http://ru.wikipedia.org/wiki/Дерево_(теория_графов).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1
3
1 1 2 1
2 1
2 2
|
2
1
|