Trong một bài toán xác suất, ta cần thực hiện các phép tính cộng trừ nhân chia phân số, nhưng kết quả được lấy modulo \(10^9+7\). Hãy viết chương trình xử lý \(Q\) thao tác. Mỗi phân số được biểu diễn dưới dạng cặp \((tử, mẫu)\).

Định dạng đầu vào

• Dòng đầu: số nguyên \(Q\) (\(1 \le Q \le 10^5\)) và modulo \(MOD\) (\(MOD\) nguyên tố, \(MOD \le 10^9\)).
• \(Q\) dòng tiếp, dòng thứ \(i\) có một trong các dạng:
  • 1 x y: thêm phân số \(x / y\) vào tập hợp
  • 2: in ra tổng các phân số trong tập hợp (dạng tối giản, modulo \(MOD\))

Định dạng đầu ra

• Với mỗi thao tác loại 2, in ra \(tử \times mẫu^{-1} \bmod MOD\).

Ví dụ

Input:

5 1000000007
1 1 2
1 1 3
2
1 1 6
2

Output:

83333334
0

Giải thích: \(1/2 + 1/3 = 5/6\). \(5 \times 6^{-1} \bmod MOD = 5 \times 166666668 = 833333340 \bmod MOD = 83333334\).

Ràng buộc

• 100% số điểm: \(Q \le 10^5\), \(MOD\) nguyên tố, giá trị tử mẫu không quá \(10^9\).