G. Inspeção dos picos

Time limit: 4000 msMemory limit: 256 MB

Uma sequência contém uma permutação de $1$ a $n$ . Um inspetor escolhe uma ordem para examinar os $n$ elementos originais, examinando cada um exatamente uma vez.

Quando um elemento é examinado, ele é apagado se for maior do que todos os seus vizinhos imediatos na sequência atual. Caso contrário, ele permanece e nunca mais é examinado. Nas extremidades há apenas um vizinho; o único elemento de uma sequência de tamanho $1$ é sempre apagado quando examinado. Após um apagamento, os elementos restantes se aproximam, preservando a ordem.

Conte quantas das $n!$ ordens de inspeção produzem exatamente $k$ apagamentos, módulo $10^9+7$ . Duas ordens são diferentes se examinam elementos diferentes em alguma etapa, mesmo que produzam a mesma sequência final.

Input

A primeira linha contém $n$ e $k$ ( $1 \le n \le 3500$ , $0 \le k \le n$ ). A segunda contém uma permutação de a .

Output

Imprima o número de ordens de inspeção com exatamente $k$ apagamentos, módulo $10^9+7$ .

Samples

Sample 1

Input

3 2
2 1 3

Output

Os elementos $2$ e $3$ são sempre apagados. O elemento $1$ só é apagado se for o último a ser examinado. Há quatro ordens nas quais ele não é o último.