UCLN hai dãy

Cho dãy \(a\) gồm \(n\) số và dãy \(b\) gồm \(m\) số. Hãy tính giá trị:

trong đó \(\prod_{i=1}^{n} a_i\) là tích các số trong dãy \(a\) và \(\prod_{j=1}^{m} b_j\) là tích các số trong dãy \(b\).

Input

• Dòng đầu chứa hai số nguyên \(n, m\) (\(1 \le n, m \le 5\cdot 10^5\)).

• Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) (\(1 \le a_i \le 10^7\)).

• Dòng thứ ba chứa \(m\) số nguyên dương \(b_j\) (\(1 \le b_j \le 10^7\)).

Output

In ra một số nguyên duy nhất là ước chung lớn nhất của hai tích, lấy dư khi chia cho \(10^9+7\).

Notes

Với \(a = (2, 3, 4)\) và \(b = (6, 8)\): hai tích là \(24\) và \(48\), ước chung lớn nhất là \(24\).