Nhóm A có ~N~ thí sinh, mỗi thí sinh có sức mạnh bằng ~a_i~, nhóm B có ~M~ thí sinh, mỗi thí sinh có sức mạnh bằng ~b_i~.

Luật thi đấu đối kháng như sau: Mỗi nhóm 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.

Bon muốn tính xem có bao nhiêu cách 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í sinh đến từ nhóm A luôn chiến thắng.

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~N, M, K~ ~(1 \le N, M \le 1000; 1 \le K \le 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 \le a_i, b_i \le 10^9)~.

Output

In ra đáp án tìm được theo modulo ~10^9 + 9~.

Scoring

Sample Input 1

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

Sample Output 1

2

Notes

Nhóm A chọn ~(2, 6, 7)~, nhóm B chọn ~(1, 3, 6)~. Nhóm A có ~2~ cách chọn bộ ~(2, 6, 7)~ tương ứng với ~2~ cách.