Gigel estudió recientemente cadenas con ~n~ elementos, números naturales. Para tal cadena ~S~, Gigel quiere encontrar la respuesta a las preguntas para un ~V~ dado:

~a)~ Si ~V = 1~, ¿cuál es el número mínimo de subconjuntos estrictamente crecientes en las que ~S~ puede dividirse?

~b)~ Si ~V = 2~, ¿cuál es el número de secuencias, módulo ~20011~, con la suma de los elementos divisibles por ~k~ que se pueden obtener de ~S~?

Si ~V = 3~, determine los dos casos.

Tarea

Dada una cadena ~S~ con ~n~ elementos, números naturales y un número natural ~k~ se le pide que responda las dos preguntas.

Datos de entrada

La entrada estárdar en la primera línea están los valores naturales ~n~, ~k~ y ~v~ separados por un espacio. En la siguiente línea están los ~n~ elementos de la cadena ~S~, números naturales separados por un espacio.

Datos de salida

La salida estárdar contendrá dos líneas, si ~v = 1~ se escribirá en la primera línea un número natural que representa la respuesta a la pregunta ~a)~, si ~v = 2~, un número natural que representa la respuesta a la pregunta ~b)~. Si ~v = 3~ se responderán los dos casos, uno en cada línea.

Restricciones y especificaciones:

• ~1 \le v \le 3~
• ~1 < n < 100,000~
• Tiene elementos menores o iguales a ~20,000~
• ~k < 50 000~, ~k < n~
• Una cadena de la cadena S se obtiene seleccionando elementos de ~S~ en el orden en que están en ~S~, pero no necesariamente de posiciones consecutivas, y una secuencia de cadena ~S~ se obtiene seleccionando elementos en el orden en que están en ~S~, pero necesariamente de puestos consecutivos También se permiten secuencias de un elemento o subcadenas.
• Para el ~50~ % de las pruebas ~k < 10,000~
• Se otorga el ~20~ % de la puntuación por la respuesta correcta al requisito ~V = 1~.
• Se otorga el ~30~ % de la puntuación por la respuesta correcta al requisito ~V = 2~.
• Se otorga el ~50~ % de la puntuación por la respuesta correcta al requisito ~V = 3~.
• Varias subredes de ~S~ forman una partición si los elementos de la reunión de la subunidad pueden redimensionarse para que se obtenga exactamente ~S~.
• ~x~ módulo y representa el resto de la división de ~x~ en ~y~.
• En caso de que no haya podido resolver el requisito a), pero tiene una respuesta para b), ¡escribirá la respuesta para el requisito b) en la línea ~2~ y no en la primera línea!

Ejemplo de Entrada

10 3 3              
5 3 8 6 9 6 2 7 9 6

Ejemplo de Salida

4
23

Explicaciones

Como ~v = 3~ se responderá los dos casos.

a) Una partición con un número mínimo (~4~) de subconjuntos crecientes es la siguiente:

~5 6 7 9~ ~3 6 9~ ~8~ ~2 6~

b) Hay ~23~ secuencias con la suma divisible por ~3~. Aquí hay dos de ellas: ~3~ ~6 2 7~