Giải bài trực tuyến

Một lần tham gia Hôi thảo Ven Biển, Đại-Ca-Đi-Học làm quen với một cô giáo rất xinh đẹp. Đại-Ca quyết định sẽ tham dự giở bài giảng Số học Kỳ tuyệt của cô giáo.

Cô giáo giảng bài: "Ước số và bội số là một trong những khái niệm quen thuộc trong số học. 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 a₁,a₂,...,a_K bất kỳ, ước số chung lớn nhất của chúng là số nguyên dương X lớn nhất thỏa mãn mọi a_i là bội số của X. Tương tự, bội số chung nhỏ nhất của chúng là số nguyên dương Y nhỏ nhất thỏa mãn mọi a_i là ước số của Y."

Chợt để kiểm tra xem Đại Ca Đi Học có thật sự tập trung vào bài giảng hay không, cô giáo ra một bài toán khá hóc búa sau đây:

Bài toán: Cho 2 dãy số nguyên p₁,p₂,...,p_M và q₁,q₂,...,q_N. Đặt P=p₁*p₂*...*p_M và Q=q₁*a₂*...*q_N. Đế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. 

Input

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

- Dòng thứ hai gồm M số nguyên dương p₁,p₂,...,p_M.

- Dòng thứ ba gồm N số nguyên dương q₁,q₂,...,q_N.

Output

- Gốm một số nguyên duy nhất là số bộ số thỏa mãn. Do kết quả có thể rất bé nên chỉ cần in ra phần dư khi chia cho 10⁹+9.

Example

Input:

1 2 2

1

2 3

Output:

4

Input:

1 2 10

2

2 2

Output:

1022

Constraint

- Trong tất cả các test: K<=10⁹. Các số nguyên còn lại trong file input có giá trị tuyệt đối không quá 10⁶.

- Trong 3 test đầu tiên, M=N=K=1.

- Trong 6 test tiếp theo, max(P,Q)<=10⁶ và K=2.

- Trong 9 test tiếp theo, max(M,N)<=5000 và K=2.

- Trong 7 test tiếp theo, K=2.

- Trong 10 test cuối cùng, không có ràng buộc gì thêm