Đếm ước tích cặp số


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.