题目描述

每年，农民约翰都会带着他的${N}$头牛参加州集市上的"最佳表演"比赛。他的主要对手，农民保罗，也带着他的${M}$头牛参加比赛${（1≤}$${N≤}$${1000,1≤}$${M≤}$${1000).}$

活动中的每头${N+M}$奶牛都获得一个单独的整数分。然而，今年的决赛将根据${K}$头奶牛的队伍来决定${（1≤}$${K≤}$${10）}$ 具体内容如下：农夫约翰和农夫保罗都选择了各自奶牛中的${K}$只进行比赛。然后将这两个团队中的奶牛配对：${FJ}$团队中得分最高的奶牛与${FP}$团队中得分最高的奶牛配对，${FJ}$团队中得分第二高的奶牛与${FP}$团队中得分第二高的奶牛配对，依此类推。如果在每一对中，他的奶牛得分较高，${FJ}$获胜。

请帮助${FJ}$统计他和${FP}$选择团队的不同方式的数量，以便${FJ}$赢得比赛。也就是说，应该统计${FJ}$获胜的每个不同对（${FJ}$的${K}$头奶牛集，${FP}$的${K}$头奶牛 集）。以${1000000009}$为单位打印答案。

输入格式

第一行输入包含${N}$、${M}$和${K}$。${K}$的值将不大于${N}$或${M}$。

下一行包含${FJ}$奶牛的${N}$分。

最后一行包含${FP}$奶牛的${M}$分数。

输出格式

打印${FJ}$和${FP}$选择团队的方式数，使${FJ}$获胜，模${100000009}$。

样例

输入样例

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

输出样例

382