Construyendo el equipo.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C#, C++, Java, Pascal, Python, VB

Todos los años, el granjero John lleva sus N vacas para competir por el "mejor de la exposición" en la feria estatal. Su archirrival, el granjero Paul, lleva también sus M vacas para competir (1 \leq N \leq 1000, 1 \leq M \leq 1000).

Cada una de las N + M vacas del certamen recibe una puntuación individual entera. Sin embargo, la competición final de este año se determinará en base a equipos de K vacas ( 1 \leq K \leq 10), como sigue: El granjero John y el granjero Paul seleccionan equipos de K de sus respectivas vacas para competir. Las vacas de estos dos equipos se emparejan: la vaca con mayor puntuación del equipo de GJ se empareja con la vaca con mayor puntuación del equipo de GP, la segunda vaca con mayor puntuación del equipo de GJ se empareja con la segunda vaca con mayor puntuación del equipo de GP, y así sucesivamente. GJ gana si en cada uno de estos emparejamientos, su vaca tiene la mayor puntuación.

Ayude a GJ a contar el número de formas diferentes en que él y GP pueden elegir sus equipos de manera que GJ gane el concurso. Es decir, hay que contar cada par distinto (conjunto de K vacas para GJ, conjunto de K vacas para GP) en el que GJ gane. Imprima su respuesta en módulo 10^9 + 7.

Entrada

La primera línea de entrada contiene N, M y K. El valor de K no será mayor que N o M.

La siguiente línea contiene las N puntuaciones de las vacas de GJ.

La última línea contiene las puntuaciones M de las vacas de GP.

Salida

Imprime el número de formas en las que FJ y FP pueden elegir equipos de forma que GJ gane, módulo 10^9 + 7.

Ejemplo de Entrada

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

Ejemplo de Salida

382

Comments

There are no comments at the moment.