Xây Dựng Đội

Hàng năm, nông dân John mang $N$ con bò của mình đến tham dự hội chợ tiểu bang để tranh tài. Đối thủ của anh ta, nông dân Paul, cũng mang $M$ con bò đến thi đấu ($1\le N\le 1000$, $1\le M\le 1000$).

Mỗi con bò trong số $N+M$ con bò tham dự đều nhận được một điểm số nguyên riêng lẻ. Tuy nhiên, cuộc thi năm nay sẽ được quyết định dựa trên các đội gồm $K$ con bò ($1\le K\le 10$) như sau: nông dân John và nông dân Paul đều chọn ra đội gồm $K$ con bò từ đàn của mình để thi đấu. Các con bò trong hai đội sau đó được ghép đôi theo thứ tự: con bò có điểm cao nhất trong đội của FJ được ghép với con bò có điểm cao nhất trong đội của FP, con bò cao điểm thứ hai của FJ ghép với con bò cao điểm thứ hai của FP, và cứ tiếp tục như vậy. FJ thắng nếu trong mỗi cặp đó, con bò của anh ta có điểm cao hơn.

Hãy giúp FJ đếm số cách khác nhau mà anh ta và FP có thể chọn đội sao cho FJ thắng. Tức là, đếm số cặp phân biệt (tập $K$ con bò của FJ, tập $K$ con bò của FP) sao cho FJ thắng. In kết quả theo modulo $1.000\mathrm{.000}\mathrm{.009}$.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $N$, $M$, $K$. Giá trị $K$ không lớn hơn $N$ hoặc $M$.
• Dòng tiếp theo chứa $N$ số nguyên là điểm số của $N$ con bò của FJ.
• Dòng cuối cùng chứa $M$ số nguyên là điểm số của $M$ con bò của FP.

Dữ liệu ra

In ra số cách FJ và FP có thể chọn đội sao cho FJ thắng, lấy modulo $1.000\mathrm{.000}\mathrm{.009}$.

Ràng buộc

• $1\le N\le 1000$
• $1\le M\le 1000$
• $1\le K\le min(N,M)$, $K\le 10$
• Điểm số các con bò là số nguyên dương không vượt quá ${10}^9$

Ví dụ

Ghi chú

• Trong ví dụ 1: FJ phải chọn 3 con bò và FP cũng chọn 3 con bò, sau đó ghép đôi theo thứ tự điểm giảm dần. FJ thắng khi mỗi con bò của anh ta đánh bại con bò tương ứng của FP.
• Các con bò có thể có điểm số bằng nhau, nhưng điều đó không đủ để FJ thắng — FJ phải nghiêm ngặt cao hơn trong mỗi cặp.