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.

Dữ liệu

• 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ả

-In ra đáp án tìm được theo modulo \(10^9+9\)

Sample Input

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

Sample Output

2