当前没有测试数据。

题目描述

在星际联盟中，有两个星球——光辉星球和影子星球。这两个星球每年都会举行一场盛大的星际竞技赛，比拼智慧与力量。

竞技赛规则如下：

• 阿尔法会派出来自光辉星球的 $N$ 位战士参加比赛，而贝塔则派出影子星球的 $M$ 位战士。
• 每位战士都有一个整数的战力值。
• 比赛的关键环节是双方各挑选战士组成一支精英小队。阿尔法和贝塔都要从各自的战士中挑选出 $C$ 位战士组队，参加最终的对决。
• 最终对决方式为：两支小队的战士将按照战力值从高到低依次进行比拼。光辉星球小队中战力值最高的战士将与影子星球小队中战力值最高的战士对决，第二高的对决第二高的，依此类推。

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

你的任务是计算出，在所有可能的选拔方案中，光辉星球能够获胜的方案总数，并输出这个数值对 $10^9+7$ 取模的结果。

输入格式

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

第二行包含 $N$ 个不递减的整数，表示光辉星球所有选手的分数。

第三行包含 $M$ 个不递减的整数，表示影子星球所有选手的分数。

输出格式

输出一个整数表示光辉星球获胜的所有选择方案，这个答案可能会很大，所以请输出方案数对 $10^9+7$ 取模的结果。

样例 #1

输入

4 4 3
4 5 6 7
3 4 5 7

输出

4

样例 #2

输入

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

输出

968

样例说明

样例 1 解释

光辉星球有 $4$ 种不同的获胜方案：

• 光辉星球选择：4 5 6，影子星球选择：3 4 5
• 光辉星球选择：4 5 7，影子星球选择：3 4 5
• 光辉星球选择：4 6 7，影子星球选择：3 4 5
• 光辉星球选择：5 6 7，影子星球选择：3 4 5

数据范围

对于所有的测评数据，满足 $1 \le N, M \le 1000$，$1 \le C \le 10$，$C \le N$，$C \le M$，每位选手的得分在 $[1, 100000]$ 范围内。

测试点	特殊性质
$1 \sim 2$	$1 \le N, M \le 10$，$C = 3$
$3 \sim 4$	$N = 10$，$M = 5$，$C = 5$
$6 \sim 10$	无