题目描述

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

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

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

输入格式

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

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

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

输出格式

打印$\red{FJ}$和$\red{FP}$选择团队的方式数，使$\red{FJ}$获胜，模$\red{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