Neko là một đại kỳ thủ trong trò chơi NEGIKO, với một biệt danh cực kì nổi tiếng là "Bố của các kỳ thủ NEGIKO". Anh ấy giỏi chơi trò này đến nỗi anh có thể nhìn thấy được có bao nhiêu cách để giành chiến thắng. Tuy nhiên, vì một ngày nọ anh ấy thức khuya leo rank thách đấu nên ngày hôm đó anh ấy không thể đếm được chính xác có bao nhiêu cách. Vì vậy nên bạn, với tư cách là bạn thân chí cốt của anh ấy, hãy tạo ra một chương trình giúp đếm số cách để Neko chiến thắng.

Biết trò chơi NEGIKO có luật chơi như sau:

Neko cầm ~n~ thẻ bài, mỗi thẻ bài có giá trị ~a_i~.

Đối thủ cầm ~m~ thẻ bài, mỗi thẻ bài có giá trị ~b_i~.

Mỗi ván chơi Neko sẽ chọn bất kì ~k~ thẻ bài của anh ấy và đối thủ sẽ chọn bất kì ~k~ thẻ bài của cậu ấy. Neko sẽ giành chiến thắng khi trong ~k~ thẻ bài từ Neko và ~k~ thẻ bài từ đối thủ được chọn:

• Thẻ bài có giá trị cao nhất của Neko lớn hơn thẻ bài có giá trị cao nhất của đối thủ
• Thẻ bài có giá trị cao thứ hai của Neko lớn hơn thẻ bài có giá trị cao thứ hai của đối thủ, ~\dots~
• Thẻ bài có giá trị cao thứ ~k~ của Neko lớn hơn thẻ bài có giá trị cao thứ ~k~ của đối thủ.

Yêu cầu: Hãy đếm số cách chọn để Neko giành chiến thắng.

Input:

• Dòng thứ nhất chứa số nguyên dương ~n~, ~m~, và ~k~ (~n \le 1000~, ~m \le 1000~, ~k \le 10~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1~, ~a_2~, …, ~a_n~ (~a_i \le 2 \times 10^5~, ~i~ = ~1~, ~2~, …, ~n~).
• Dòng thứ ba chứa ~m~ số nguyên dương ~b_1, b_2, … b_m~ (~b_i \le 2 \times 10^5~, ~i~ = ~1~, ~2~, …, ~m~).

Output:

• Số cách chia thỏa mãn yêu cầu đề bài, do đáp án có thể rất lớn nên in ra phần chia dư cho ~10^9 + 9~.

Subtask:

• ~10\%~ số test có ~n \le 10,m \le 10, k = 1~.
• ~10\%~ số test tiếp theo có ~n \le 100, m \le 100, k \le 2~.
• ~30\%~ số test tiếp theo có ~n \le 100, m \le 100~.
• Số test còn lại không có giới hạn gì thêm.

Sample Input:

3 2 2
3 4 3
2 3

Sample Output:

2

Note:

Có ~2~ cách chọn thỏa mãn:

• Neko chọn ~3~ (ở vị trí đầu) và ~4~, đối thủ chọn ~2~ và ~3~.
• Neko chọn ~3~ (ở vị trí cuối) và ~4~, đối thủ chọn ~2~ và ~3~.