Caja de puros
Aplicamos la siguiente operación veces en la secuencia , y resultó en .
- Borra un elemento. Luego, agregue el elemento borrado al principio o al final de la secuencia.
Encuentra el número de sucesiones posibles de 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
- .
es una permutación de .
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 da como resultado 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 y agréguele al principio, lo que da como resultado . Luego, borre y agréguelo al final, lo que da como resultado .
Borre y agréguelo al principio, lo que da como resultado . Luego, borre y agréguelo al final, lo que da como resultado .
Borre y agréguelo al final, lo que da como resultado . Luego, borre y agréguelo al principio, lo que da como resultado .
Borre y agréguelo al final, lo que da como resultado . Luego, borre y agréguelo al final, lo que da como resultado .
Borre y agréguelo al final, lo que da como resultado . Luego, borre y agréguelo al final, lo que da como resultado .
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 secuencias de operaciones, la mitad de todas las secuencias posibles, que queremos contar. Por lo tanto, la respuesta es módulo , es decir, .
Ejemplo de entrada 3
10 3000
3 7 10 1 9 5 4 8 6 2
Ejemplo de salida 3
129989699
Comments