Mỗi năm, Farmer John đưa \(N\) con bò của mình tới tranh tài cho danh hiệu "xuất sắc nhất cuộc thi" tại hội chợ tiểu bang. Đối thủ truyền kiếp của ông, Farmer Paul, cũng đưa \(M\) con bò của mình tới tranh tài (\(1 \leq N \leq 1000\), \(1 \leq M \leq 1000\)).

Mỗi con trong số \(N+M\) con bò tại sự kiện được chấm một điểm số nguyên. Tuy nhiên, cuộc thi chung kết năm nay sẽ được quyết định dựa trên các đội gồm \(K\) con bò (\(1 \leq K \leq 10\)) như sau: Farmer John và Farmer Paul mỗi người chọn một đội gồm \(K\) con bò của mình để tranh tài. Các con bò của hai đội sau đó được ghép cặp: con bò có điểm cao nhất trong đội của Farmer John được ghép với con có điểm cao nhất trong đội của Farmer Paul, con có điểm cao thứ hai trong đội của Farmer John được ghép với con có điểm cao thứ hai trong đội của Farmer Paul, và cứ tiếp tục như vậy. Farmer John thắng nếu trong mọi cặp, bò của ông có điểm cao hơn.

Hãy giúp Farmer John đếm số cách khác nhau mà ông và Farmer Paul có thể chọn đội sao cho Farmer John thắng cuộc thi. Nói cách khác, mỗi cặp phân biệt (một tập \(K\) con bò của Farmer John, một tập \(K\) con bò của Farmer Paul) mà Farmer John thắng đều phải được tính. In đáp án theo modulo \(1\,000\,000\,009\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) và \(K\). Giá trị \(K\) không lớn hơn \(N\) hoặc \(M\).

Dòng tiếp theo chứa điểm số của \(N\) con bò của Farmer John.

Dòng cuối cùng chứa điểm số của \(M\) con bò của Farmer Paul.

Dữ liệu ra

In số cách Farmer John và Farmer Paul có thể chọn đội sao cho Farmer John thắng, theo modulo \(1\,000\,000\,009\).

Ví dụ

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

382

Nguồn

USACO 2016 December Contest, Platinum — Team Building. Tác giả đề: Brian Dean và William Luo.

https://usaco.org/index.php?page=viewproblem2&cpid=673