Hàm băm (hash function) là một hàm số giúp chuyển dữ liệu bất kì thành một mã băm (hash code), thường có dạng một xâu có độ dài cố định. Hàm băm có ứng dụng rộng rãi trong nhiều lĩnh vực, trong đó có mật mã học (cryptography), và thậm chí là ứng dụng trong blockchain. Người ta có thể thiết kế ra một hàm băm \(f\) bất kì có tính chất sau:

• Đụng độ (hash collision) có tỉ lệ rất thấp, hầu như không xảy ra. Tức \(x \neq y \Rightarrow f(x) \neq f(y)\)
• Giả sử ta biết \(y = f(x)\), việc tìm ra \(x\) là rất khó (tốn độ phức tạp thời gian quá lớn)
• Khi đó, hàm băm có tính chất "một chiều" và có thể áp dụng được vào trong mã hóa, mật mã học.

Sau khi nghe hội thảo về những kiến thức trên, Nghĩa cảm thấy rất thú vị và muốn áp dụng ngay. Cậu muốn mã hóa hai dãy số nguyên dương \(a,b\) có kích thước lần lượt là \(n, m\) phần tử. Cậu định nghĩa:

• \(A = a_{1} \times a_{2} \times \dots \times a_{n}\) (tích các số trong dãy \(a\))
• \(B = b_{1} \times b_{2} \times \dots \times b_{m}\) (tích các số trong dãy \(b\))
• \(f(a,b) = \gcd(A, B) \mod (10^{9} + 7)\), tức là ước chung lớn nhất của tích hai dãy, chia lấy dư cho \((10^{9} + 7)\) vì số rất lớn.

Nghĩa nhận thấy hàm \(f\) trên có tính chất "một chiều" như đã nêu trên, nhưng do cậu không giỏi lắm về tin học nên chưa thiết kế được thuật toán hiệu quả để tính \(f\). Nghĩa cần được các bạn thí sinh THT trợ giúp!

Yêu cầu: Cho hai dãy \(a,b\), hãy tính và in ra \(f(a, b)\)

Input

• Dòng thứ nhất chứa hai số nguyên \(n, m\) \((1 \leq n, m \leq 5 \times 10^{5})\) - lần lượt là kích thước hai dãy.
• Dòng thứ hai chứa \(n\) số nguyên \(a_{i}\) \((1 \leq a_{i} \leq 10^{7})\).
• Dòng thứ ba chứa \(m\) số nguyên \(b_{i}\) \((1 \leq b_{i} \leq 10^{7})\).

Output

• Gồm một dòng duy nhất chứa \(f(a, b)\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, m \leq 14\) và \(a_{i}, b_{i} \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm): \(n = 1\)
• Subtask \(3\) (\(20\%\) số điểm): \(n, m, a_{i}, b_{i} \leq 10^{5}\)
• Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm

Example

4 4
5 3 2 18
6 7 10 3

180