Susan es buena organizando su mesa de comedor para que resulte cómoda, pero no su escritorio de oficina.
Susan acaba de terminar el trabajo con un conjunto de documentos que todavía están apilados en su escritorio. Tienen números de serie y estaban apilados en orden cuando su jefe los trajo. Sin embargo, ahora el orden no es perfecto, ya que le dio pereza devolver a sus posiciones correctas los documentos que había sacado de la pila. Al enterarse de que ha terminado, el jefe quiere que devuelva inmediatamente los documentos en la caja que le está enviando. Por supuesto, los documentos deben guardarse en la caja en el orden de sus números de serie.
En el escritorio hay espacio justo para otras dos pilas de documentos, donde Susan planea crear dos pilas temporales. Todos los documentos de la pila actual se moverán uno a uno desde la parte superior a cualquiera de las dos pilas temporales. Como apilarlas demasiado alto con prisas podría hacerlas caer, no deben colocarse demasiados documentos en ellas. Después de mover todos los documentos a las pilas temporales y recibir la caja, se moverán desde la parte superior de ambas pilas, uno a uno, a la caja. Los documentos de las dos pilas deben estar en orden inverso de sus números de serie para poder moverlos a la caja en orden.
Por ejemplo, supongamos que la pila tiene seis documentos $1,3,4,2,6,5$, en ese orden desde arriba, y que las pilas temporales pueden tener como máximo tres documentos. Puede crear una pila con $6,4,3$ desde arriba y otra con $5,2,1$ (véase la imagen). Ambas están en orden inverso. Después compara los números de serie de los documentos superiores de ambas pilas; el de mayor número ($6$ en este caso) se retira y se guarda primero en la caja. Repitiendo esto, todos los documentos quedarán perfectamente ordenados en la caja.
Susan se pregunta si el plan es viable para los documentos de la pila actual y, de ser así, cuántas formas distintas de apilarlos en dos pilas temporales sirven. Ayuda a Susan escribiendo un programa que calcule el número de formas, que debe ser cero si el plan no es viable.
Como cada documento puede moverse a cualquiera de las dos pilas temporales, para $n$ documentos hay en total $2^n$ combinaciones de elecciones. Sin embargo, algunas pueden alterar el orden inverso de las pilas temporales y, por tanto, son inadecuadas.
El ejemplo anterior corresponde al primer caso de la entrada de ejemplo. En este caso, los dos últimos documentos, $5$ y $6$, pueden intercambiar sus destinos. También se pueden intercambiar completamente los papeles de las dos pilas temporales. Como cualquier otra secuencia de movimientos haría que una pila tuviera más de tres documentos o que se perdiera el orden, el número total de formas distintas de apilar documentos en las pilas temporales de este ejemplo es $2\times2=4$.
Entrada
La primera línea de la entrada contiene dos enteros $n,m$. $n$ es el número de documentos de la pila ($1\le n\le5000$), y $m$ es el número de documentos que pueden apilarse en una pila temporal sin correr el riesgo de que caiga ($n/2\le m\le n$). La siguiente línea contiene los números de $s_1$ a $s_n$, que son los números de serie de los documentos de la pila, de arriba abajo. Se garantiza que todos los números del $1$ al $n$ aparecen exactamente una vez.
Salida
Imprime en una línea un único entero que indique el número de formas de crear dos pilas temporales adecuadas para el objetivo.
Si ninguna elección sirve, el número de formas es, por supuesto, $0$. Si el número de formas posibles es mayor o igual que $10^9+7$, imprime el número de formas módulo $10^9+7$.
Ejemplos
Entrada 1
6 3 1 3 4 2 6 5
Salida 1
4
Entrada 2
6 6 1 3 4 2 6 5
Salida 2
8
Entrada 3
4 4 4 3 1 2
Salida 3
0