Trong một tiết học toán của lớp chuyên Tin học, thầy giáo Hoa đang giảng bài: về Ước số và bội số là một trong những khái niệm quen thuộc trong số học cho học sinh lớp chuyên Tin.

Với 2 số nguyên A và B bất kỳ, nếu A chia hết cho B, ta nói A là bội số của B và B là ước số của A. Với một bộ K số nguyên dương a1, a2,…, aK bất kỳ, ước số chung lớn nhất của chúng là số nguyên X lớn nhất thỏa mãn mọi ai là bội số của X. Tương tự, bội số chung nhỏ nhất của bộ số này là số nguyên Y nhỏ nhất thỏa mãn mọi ai là ước số của Y. Bất chợt học sinh Phát trong lớp nghĩ ra một bài toán: Cho 2 dãy số nguyên p1, p2,…, pM và q1, q2,…, qN. Đặt P= p1.p2.p3…pM và Q= q1.q2.q3…qN. Đếm số bộ K số nguyên có ước số chung lớn nhất là P và bội số chung nhỏ nhất là Q.

Yêu cầu: Các bạn là gương mặt ưu tú tuyển chọn của trường hãy giúp Phát giải bài toán này nhé.

Dữ liệu vào: Từ tệp văn bản MATH.INP gồm:

Dòng đầu tiên gồm ba số nguyên dương M, N, K;

Dòng thứ hai gồm M số nguyên dương p1,p2,…, pM;

Dòng thứ ba gồm N số nguyên dương q1, q2,…, qN.

Các số trên một dòng của tệp dữ liệu vào được ghi cách nhau bởi dấu cách.

Kết quả ra: Ghi ra tệp văn bản MATH.OUT gồm: Một số nguyên duy nhất là số bộ số thỏa mãn. Kết quả của bài toán chỉ cần in ra phần dư khi chia cho 10^9+9.

Ví dụ 1:

MATH.INP

1 2 2
1
2 3 

MATH.OUT

4

Giải thích

P=1; Q=6. 4 bộ 2 số thỏa mãn điều kiện là (1,6), (2,3), (3,2), (6,1).

Ví dụ 2:

MATH.INP

2 1 2
2 5 
131 

MATH.OUT

0

Giải thích

P=10; Q=131. Do Q không chia hết cho P nên dễ thấy không tồn tại bộ số nào thỏa mãn.

Ràng buộc: Trong tất cả bộ test: K≤10^9, các số còn lại trong tệp dữ liệu vào có giá trị tuyệt đối không quá 10^6.

Có 10% số test ứng với 10% số điểm của bài có M=N=K=1;

Có 30% số test ứng với 30% số điểm của bài có max(P, Q) ≤ 3 và K=2; 3x10^3 và K=2;

Có 20% số test ứng với 20% số điểm của bài có max(P, Q) ≤ 10^6 và K=2;

Có 20% số test ứng với 20% số điểm của bài có max(M, N) ≤ 5x10^3 và K=2;

Có 20% số test khác ứng với 20% số điểm còn lại của bài.