时间限制：1秒　　内存限制：256M

---

【题目描述】

　　每年农夫约翰都会带着他的 \(N\) 只牛去集会上参加“你是最棒哒“的比赛。他的对手农夫保罗也带了 \(M\) 只牛去参加比赛。每只牛都有自己的分数。两人会选择 \(K\) 只牛组成队伍，两队牛在按分数大小排序后一一配对，并且约翰打败保罗当且仅当对于每一对牛，约翰的牛分数都比保罗的高。请帮助约翰计算约翰打败保罗的方案数 \(mod\ 1000000009\)。两种方案不同，当且仅当约翰或保罗选择的牛的集合与另一种方案不同。

【输入格式】

　　第一行是整数 \(N, M\) 和 \(K\)。
　　第二行包含 \(N\)个整数，表示约翰的 \(N\) 头牛的分数。
　　第三行包含 \(M\) 个整数，表示保罗的 \(M\)头牛的分数。

【输出格式】

　　约翰计算约翰打败保罗的方案数 \(mod\ 1000000009\)。

【输入输出样例】

　Input

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

　Output

382

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N,M≤1000\)，\(1≤K≤10\)。

【来源】

　　Mr.he