Trong kỳ thi chọn Học sinh giỏi Duyên Hải – Hải Dương 2024 có bài toán tìm ước chung lớn nhất của hai số nguyên dương ~X~ và ~Y~. Thỏa mãn điều kiện: ~X = x[1] \times x[2] \times \dots \times x[n]~ ~Y = y[1] \times y[2] \times \dots \times y[m]~ Biết ~n~ số nguyên nhỏ mà có tích là ~X~ và ~m~ số nguyên nhỏ có tích là ~Y~.

Yêu cầu: Hãy viết chương trình tìm ước chung lớn nhất của ~X~ và ~Y~. Do kết quả có thể là rất lớn và bạn chỉ cần in ra số dư của phép chia modulo ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^3~)
• Dòng thứ hai chứa ~n~ số nguyên dương ~x[1], x[2], \dots, x[n]~ (~1 \le x[i] \le 10^5~)
• Dòng đầu tiên chứa số nguyên dương ~m~ (~1 \le m \le 10^3~)
• Dòng thứ hai chứa ~m~ số nguyên dương ~y[1], y[2], \dots, y[m]~ (~1 \le y[i] \le 10^5~)

Output

• Gồm một dòng ghi một số ~k~ duy nhất là ước chung lớn nhất của ~X~ và ~Y~. Vì ~k~ có thể rất lớn, in ra số dư của phép chia ~k~ cho modulo ~10^9 + 7~.

Sample Input 1

3
4 5 6
3
8 4 5

Sample Output 1

40