Trong Toán 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_1, a_2, \dots, a_K~ 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 ~a_i~ 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 ~a_i~ là ước số của ~Y~.

Cho ~2~ dãy số nguyên ~p_1, p_2, \dots, p_M~ và ~q_1, q_2, \dots, q_N~. Đặt ~P = p_1 \times p_2 \times \dots \times p_M~ và ~Q = q_1 \times q_2 \times \dots \times q_N~.

Yêu cầu: Hãy lập trình đế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 ba số nguyên dương ~M, N, K~;
• Dòng thứ hai gồm ~M~ số nguyên dương ~p_1, p_2, \dots, p_M~;
• Dòng thứ ba gồm ~N~ số nguyên dương ~q_1, q_2, \dots, q_N~.

Output

• 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~.