Xuân tóc đỏ, truyền nhân của Shank tóc đỏ là một tay chơi cá cược chính hiệu. Anh luôn thắng trong những trò cá cược mình tham gia. Hôm nay đối thủ cá cược của Xuân là Phán mọc sừng.

Trò chơi này gồm một cái máy có \(n\) hộp được đánh số từ \(1\) đến \(n\) và \(n-1\) đường ống nối \(n\) những cái hộp với nhau đảm bảo tạo thành cây. Hộp \(1\) là hộp cao nhất và các hộp còn lại có độ cao giảm dần, khi thả một viên bi vào hộp \(1\) thì nó sẽ rơi dần xuống các hộp phía dưới và dừng lại khi bị chặn. Khi viên bi rơi xuống một hộp \(u\) thì xác suất viên bi rơi xuống tiếp những hộp con là như nhau ( khi viên bi rơi xuống một hộp không có hộp con thì viên bi sẽ nằm lại hộp đó).

Vì đây là một cái máy tiên tiến nên mỗi hộp đều có một vách ngăn có thể đóng mở, khi ta dùng điều khiển chọn một hộp nào đó thì nếu vách ngăn ở hộp đó mở thì nó sẽ đóng lại và ngược lại. Nếu vách ngăn ở một hộp đóng thì khi rơi viên bi sẽ bị chặn ở hộp đó, ban đầu vách ngăn ở mọi hộp đều mở.

Bây giờ Xuân sẽ thực hiện lần lượt \(q\) thao tác:

• \(1\)ㅤ\(u(1 \le u \le n):\) Tìm xác xuất để viên bi dừng lại ở hộp \(u\).

• \(2\)​​‍‍ㅤ\(u(1 \le u \le n):\) Bật tắt vách ngăn ở hộp \(u\).

Input

• Dòng đầu lần lượt là \(2\) số \(n,q\).

• \(n-1\) dòng tiếp theo mỗi dòng là \(2\) số \(u,v(u,v \le n)\) biểu thị việc có đường ống nối giữa \(2\) hộp \(u\) và \(v\).

• \(q\) dòng tiếp theo tương đương với \(q\) truy vấn.

Output

- Ứng với mỗi truy vấn loại \(1\) thì trên mỗi dòng, nếu xác suất là \(0\) thì in ra \(0\), nếu xác suất là phân số tối giản \(a/b\) (\(a,b>0\)) thì in ra \(a\) và \(b\) khi chia lấy dư cho \(10^9+7\) cách nhau một dấu cách.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le n,q \le 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(1 \le n,q \le 5*10^5\) và không có truy vấn loại \(2\).
• Subtask \(3\) (\(50\%\) số điểm): \(1 \le n,q \le 5*10^5\).

Example

7 10
1 2
4 2
1 3
2 5
6 2
7 5
1 1
1 7
2 3
1 3
2 1
2 2
1 1
1 2
2 1
1 2

0
1 6
1 2
1 1
0
1 2