Minh được thầy giáo giao cho một bài tập về nhà là tìm ước số chung lớn nhất của hai số nguyên dương ~A~ và ~B~. Tuy nhiên, do các số này là khá lớn, thầy giáo cho cậu biết ~N~ số nguyên nhỏ mà có tích là ~A~ và ~M~ số nguyên nhỏ mà có tích là ~B~. Nói cách khác, Minh được biết hai dãy ~a[1], a[2], ..., a[N], b[1], b[2], ..., b[M]~ thỏa mãn điều kiện:

• A = a[1] × a[2] × ... × a[N];
• B = b[1] × b[2] × ... × b[M].

Minh cần phải tìm ước số chung lớn nhất của ~A~ và ~B~.

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

Dữ liệu:

• 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 ~a[1], a[2], ..., a[N] (1 \le a[i] \le 10^5, 1 \le i \le N)~ có tích bằng ~A~;
• Dòng thứ ba chứa số nguyên dương ~M (1 \le M \le 10^3)~;
• Dòng thứ tư chứa ~M~ số nguyên dương ~b[1], b[2], ..., b[M] (1 \le b[i] \le 10^5, 1 \le i \le M)~ có tích bằng ~B~.

Kết quả:

• Ghi ra một dòng ghi một số ~X~ duy nhất là ước chung lớn nhất ~A~ và ~B~. Vì ~X~ có thể rất lớn, bạn chỉ cần in ra số dư của phép chia ~X~ cho ~(10^9 + 7)~.

Ràng buộc:

• Có ~50\%~ số điểm của bài có: ~1 \le M, N \le 10, 1 \le a[i], b[j] \le 50 (1 \le i \le N, 1 \le j \le M)~;
• Có ~50\%~ số điểm của bài có: ~1 \le M, N \le 10^3, 1 \le a[i], b[j] \le 10^5 (1 \le i \le N, 1 \le j \le M)~.

Ví dụ:

Sample Input 1

3
2 3 5
2
4 5

Sample Output 1

10

Sample Input 2

4
6 2 3 4
1
1

Sample Output 2

1

Giải thích:

• Ví dụ ~1~: ~A = 2 × 3 × 5 = 30, B = 4 × 5 = 20~ và ~GCD(A, B) = 10~.
• Ví dụ ~2~: ~A = 2 × 3 × 4 × 6 = 144, B = 1~ và ~GCD(A, B) = 1~.