在遥远的宇宙中，有两个星球——光辉星球和影子星球。这两个星球每年都会举行一场盛大的 星际竞技赛，比拼智慧与力量。光辉星球的领袖阿尔法（Alpha）和影子星球的领袖贝塔（Beta）都希望通过这场比赛来展现星球的荣耀。

竞技赛规则如下：

阿尔法会派出来自光辉星球的 N 位战士参加比赛，而贝塔则派出影子星球的 M 位战士。

每位战士都拥有一个独特的 战力值，这些战力值是由评委们根据战士们的表现打分决定的。

比赛的关键环节是挑选战士组成一支精英小队。阿尔法和贝塔都要从各自的战士中挑选出 K 位战士组队，参加最终的对决。

最终的对决方式为：两支小队的战士将按照战力值从高到低依次进行比拼。光辉星球小队中战力值最高的战士将与影子星球小队中战力值最高的战士对决，第二高的对决第二高的，以此类推。

只有当光辉星球小队的每一位战士的战力值都高于对应影子星球小队的战士时，光辉星球才被视为赢得比赛的胜利。

你的任务是计算出，在所有可能的选拔方案中，光辉星球能够获胜的方案总数，并输出这个数值对 1,000,000,009 取模的结果。

第一行包含三个整数，分别表示 N,M,K,用空格隔开；

第二行包含 n 个整数，表示光辉星球所有选手的分数；

第三行包含 m 个整数，表示影子星球所有选手的分数。

输出一个整数表示光辉星球获胜的所有选择方案，这个答案可能会很大，所以请输出输出方案数对 1\,000\,000\,009 取模的结果。

【数据规模】

1 \leq n,m \leq 1000;

1 \leq k \leq 10 。

数据保证 k 不会超过 n 和 m 。

月赛动态规划