E. Festival de música
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

En un festival de música se van a reproducir n canciones en orden aleatorio. Algunas canciones animan más al público que otras; en concreto, se sabe que el público le da una nota ai a la i-ésima canción.

Decimos que se produce un cuando se reproduce una canción que es mejor que la anterior según el público; es decir, si las canciones se reproducen siguiendo una permutación de índices p (donde p es una permutación de {1, 2, ..., n}), decimos que la posición i-ésima (para 2 ≤ i ≤ n) es un subidón si api > api - 1. Decimos que una reproducción de canciones tiene k subidones si existen exactamente k posiciones que son un subidón.

Dado k, cuenta cuántas permutaciones p existen tales que, si se reproducen las canciones siguiendo la permutación p (primero ap1, después ap2, etc.), hay exactamente k subidones. Como este número puede ser muy grande, da la respuesta módulo 109 + 7.

Input

La primera línea de la entrada contiene el número de casos T.

Por cada caso, habrá una línea de entrada con los enteros n y k.

La siguiente línea de cada caso contiene n enteros ai, las notas del público para las n canciones.

Output

Para cada caso, debes imprimir un entero: el número de permutaciones, módulo 109 + 7, que producen exactamente k subidones.

Scoring
  1. (8 puntos) La suma de n para todos los casos es como mucho 9.
  2. (21 puntos) k = 0.
  3. (32 puntos) a es una permutación de {1, 2, ..., n}.
  4. (39 puntos) Sin restricciones adicionales.
Example
Input
3
3 1
1 2 3
4 2
3 3 2 2
5 4
3 3 3 3 3
Output
4
4
0
Note
  • 1 ≤ T ≤ 2000
  • 1 ≤ n ≤ 2000
  • 0 ≤ k ≤ n - 1
  • La suma de n para todos los casos es como mucho 2000.
  • 1 ≤ ai ≤ 109

En el primer caso, tenemos 3 canciones con notas 1, 2 y 3 y queremos conseguir exactamente 1 subidón. Existen 6 permutaciones posibles de los índices. Si analizamos las secuencias de notas que generan:

  • Si reproducimos las canciones en el orden de índices [1, 2, 3], las notas son 1, 2, 3. Hay 2 subidones (de 1 a 2, y de 2 a 3).
  • Si el orden es [3, 2, 1], las notas son 3, 2, 1. Hay 0 subidones.
  • Los 4 órdenes restantes generan exactamente 1 subidón. Por ejemplo, el orden de índices [1, 3, 2] genera las notas 1, 3, 2, donde solo el salto de 1 a 3 es un subidón. Las otras válidas son [2, 1, 3], [2, 3, 1] y [3, 1, 2]. Por lo tanto, la respuesta es 4.

En el segundo caso, tenemos 4 canciones con notas 3, 3, 2, 2 y queremos exactamente 2 subidones. Para conseguir 2 subidones con estas notas, la única estructura válida para la secuencia reproducida es alternar las notas bajas y altas: 2, 3, 2, 3. Como permutar los índices importa, las 4 permutaciones de índices válidas que generan esta secuencia de notas son: [3, 1, 4, 2], [3, 2, 4, 1], [4, 1, 3, 2] y [4, 2, 3, 1].

En el tercer caso, tenemos 5 canciones y todas tienen la misma nota (3). Queremos conseguir 4 subidones. Como la condición para un subidón es que la nota de la canción sea estrictamente mayor que la anterior (api > api - 1), es imposible conseguir un subidón si todas las notas son iguales. El número de subidones siempre será 0, por lo que existen 0 permutaciones que cumplan lo que se pide.