Đếm ước tích cặp số
Cho hai số nguyên $A$, $B$ với $A=p_1^{k_1}\times p_2^{k_2} \times ... \times p_n^{k_n}$ và $B=q_1^{l_1}\times q_2^{l_2} \times ... \times q_m^{l_m}$ ($p_1,p_2,...,p_n, q_1,q_2,...,q_m$ là các số nguyên tố).
Hãy đếm số ước của tích $A\times B$.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $n,m \ (1\le n,m \le10^5)$;
- $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $p_i, k_i \ (2\le p_1 < p_2 < ... <p_n \le 10^9; 1\le k_i \le 10^5)$;
- $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $q_i, l_i \ (2\le q_1 < q_2 < ... <q_m \le 10^9; 1\le l_i \le 10^5)$;
Kết quả
- Kết quả bài toán sau khi chia lấy dư cho $10^9+7$.
Ví dụ
Ví dụ 1
input
2 2
2 1
3 1
3 1
5 1
output
12
Comments