Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P181PROF - ROUND 1F - Sức mạnh của cây

Cho một cây ban đầu chỉ có đỉnh gốc có chỉ số là 1. Mỗi đỉnh trong cây (gốc và các đỉnh thêm sau này) có một giá trị là vi. Sức mạnh của đỉnh S được định nghĩa:

Strength(S) = (|S|+1).(vS + ∑Strength(u))   (trong đó u là đỉnh con trực tiếp của S, |S| là số lượng đỉnh con trực tiếp của đỉnh S).

Có 2 loại truy vấn trên cây:

- Truy vấn loại 1 có dạng 1 p v, yêu cầu thêm một đỉnh mới có giá trị v làm con của đỉnh p.

- Truy vấn loại 2 có dạng 2 u, yêu cầu đưa ra sức mạnh của đỉnh u (lấy dư cho 109+7).

Input

Dòng đầu tiên chứa hai số nguyên v1, q cách nhau bởi khoảng trống (1 ≤ v1 ≤ 109, 1≤ q ≤ 200000) – giá trị của đỉnh 1 và số truy vấn.

q dòng tiếp theo, mỗi dòng mô tả một loại truy vấn:

• 1 pi vi, chỉ số của đỉnh được thêm vào là số nguyên dương nhỏ nhất chưa được sử dụng và đảm bảo rằng pi là một đỉnh đã tồn tại, 1 <= vi ≤ 109.

• 2 ui, đảm bảo đỉnh ui đã tồn tại trong cây.

Output

Với mỗi truy vấn loại 2 in ra sức mạnh của đỉnh lấy dư cho 109+7.

Example

Input:
2 5
2 5 1 1 2 1 2 4 1 3 9 1 4 10 2 1
1 1 2
1 2 4
1 3 9
Output: 348
Input:
2 5
5 5 1 1 5 1 2 4 2 2 1 2 9 2 1
Output:
18
118

Giải thích test 1:

Sức mạnh của các đỉnh trên cây lần lượt là 348 – 172 – 84 – 38 - 10


Được gửi lên bởi:adm
Ngày:2018-03-02
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.