Team A có ~n~ thí sinh, thí sinh thứ ~i~ có sức mạnh bằng ~a_i~;

Team B có ~m~ thí sinh, thí sinh thứ ~i~ có sức mạnh bằng ~b_i~.

Luật thi đấu đối kháng như sau: Mỗi team chọn ra ~k~ thí sinh, thí sinh mạnh nhất được chọn của nhóm A sẽ thi đấu với thí sinh mạnh nhất của nhóm B, thí sinh mạnh thứ 2 của nhóm A sẽ thi đấu với thí sinh mạnh thứ 2 trong nhóm B... Trong một cuộc đấu đối kháng, thí sinh nào có sức mạnh lớn hơn sẽ chiến thắng.

Ban tổ chức là người nhà của team A, vì vậy đã cố ý lựa chọn ~k~ thí sinh nhóm A và ~k~ thí sinh nhóm B sao cho trong ~k~ cuộc đấu, thành viên đến từ team A luôn chiến thắng.

Nhiệm vụ của bạn là hãy tính xem ban tổ chức có bao nhiêu cách chọn các thí sinh để đạt được mục tiêu của mình?

Dữ liệu vào:

• Dòng đầu tiên chứa 3 số nguyên ~n,m,k~ ~(1 ≤ n,m ≤ 1000,1 ≤ k ≤ 10)~.
• Dòng tiếp theo gồm ~n~ số nguyên ~a_i~.
• Dòng cuối gồm ~m~ số nguyên ~b_i~ ~(1 ≤ a_i,b_i ≤ 10^9)~.

Kết quả: Ghi đáp án tìm được theo modulo ~10^9+9~

Ràng buộc

• Có 60% số test tương ứng với ~n≤10~ hoặc ~m≤10~;
• Có 40% số test còn lại không ràng buộc gì thêm.

Ví dụ:

Input

5 10 3
1 2 2 6 7
1 3 6 8 8 9 14 17 18 19 

Output

2 

Giải thích:

Chọn tổ hợp ~(2, 6, 7)~ ở team A và tổ hợp ~(1, 3, 6)~ ở team B.

Tổ hợp ở team A được chọn 2 lần vì có 2 giá trị bằng 2 trong A