Cho 2 số nguyên dương \(a, b\) có kích thước lần lượt \(n,m\) phần tử. Được viết dưới dạng tích các số như sau:

• \(A = a_1 \times a_2 ...... \times a_n\)
• \(B = b_1 \times b_2 ...... \times b_m\)
• \(f(a,b) = gcd(A,B)\) mod \((10^9 +7)\) , tức \(f(a,b)\) là ước chung lớn nhất của tích hai dãy số (chia lấy dư cho \(10^9+7\)) vì số rất lớn.

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 \le n,m \le 5 \times 10^5\) lần lượt là số lượng phần tử của dãy \(A\) và \(B\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_i (1 \le a_i \le 10^7)\)
• Dòng thứ ba chứa \(m\) số nguyên \(b_i (1 \le b_i \le 10^7)\)

Output

• Một dòng chứa \(f(a,b)\)

Scoring

• Subtask 1 (\(30%\) số điểm): \(n,m \le 14\) và \(a_i, b_i \le 20\)
• Subtask 2 (\(30%\) số điểm): \(n=1\)
• Subtask 3 (\(20%\) số điểm): \(n,m,a_i,b_i \le 10^5\)
• Subtask 4 (\(20%\) số điểm): không ràng buộc gì thêm

Sample input 1

4 4
5 3 2 18
6 7 10 3

Ssample output 1

180