Aplicamos la siguiente operación ~m~ veces en la secuencia ~(1,2,..., n)~, y resultó en ~(a_1,..., a_n)~.

• Borra un elemento. Luego, agregue el elemento borrado al principio o al final de la secuencia.

Encuentra el número de sucesiones posibles de ~m~ operaciones válidas, módulo 998244353.

Dos secuencias de operaciones se consideran iguales cuando, en cada operación, se elige el mismo elemento y se agrega a la misma posición.

Restricciones

• ~2 \leq n, m \leq 3000~.

~a_1,..., a_n~ es una permutación de ~1,..., n~.

Entrada

La entrada se da en el siguiente formato

n m
a1, ..., an

Salida

Imprime el número de posibles secuencias de m operaciones, que al aplicarse a ~(1,2,..., n)~ da como resultado ~(a_1,..., a_n)~ módulo 998244353.

Ejemplo de entrada 1

5 2
1 2 4 5 3

Ejemplo de salida 1

5

Hay cinco posibles secuencias de operaciones, como sigue:

• Borre ~1~ y agréguele al principio, lo que da como resultado ~(1,2,3,4,5)~. Luego, borre ~3~ y agréguelo al final, lo que da como resultado ~(1,2,4,5,3)~.

• Borre ~3~ y agréguelo al principio, lo que da como resultado ~(3,1,2,4,5)~. Luego, borre ~3~ y agréguelo al final, lo que da como resultado ~(1,2,4,5,3)~.

• Borre ~3~ y agréguelo al final, lo que da como resultado ~(1,2,4,5,3)~. Luego, borre ~1~ y agréguelo al principio, lo que da como resultado ~(1,2,4,5,3)~.

• Borre ~3~ y agréguelo al final, lo que da como resultado ~(1,2,4,5,3)~. Luego, borre ~3~ y agréguelo al final, lo que da como resultado ~(1,2,4,5,3)~ .

• Borre ~5~ y agréguelo al final, lo que da como resultado ~(1,2,3,4,5)~. Luego, borre ~3~ y agréguelo al final, lo que da como resultado ~(1,2,4,5,3)~.

Ejemplo de entrada 2

2 16
1 2

Ejemplo de salida 2

150994942

Dos de los cuatro tipos de operaciones no tienen ningún efecto sobre la secuencia y los otros dos intercambian los dos elementos. A partir de este hecho, podemos demostrar que hay ~\frac{4^m}{2} = 2^{31} = 2147483648~ secuencias de operaciones, la mitad de todas las secuencias posibles, que queremos contar. Por lo tanto, la respuesta es ~2147483648~ módulo ~998244353~, es decir, ~150994942~.

Ejemplo de entrada 3

10 3000
3 7 10 1 9 5 4 8 6 2

Ejemplo de salida 3

129989699