Dice Scheherazade que muy lejos, en medio del desierto, hay un lago. Originalmente este lago tuvo ~F~ peces en él. ~K~ tipos diferentes de piedras preciosas se seleccionaron entre las de más valor en la Tierra, y a cada uno de los ~F~ peces se le dio exactamente una piedra para que se la tragara. Ten en cuenta, ya que ~K~ puede ser menor que ~F~, dos o más peces pudieron tragarse piedras del mismo tipo.

Con el tiempo, algunos peces se comieron a algunos de los otros peces. Un pez puede comerse a otro sí y solo sí este tiene al menos dos veces su longitud (el pez A puede comerse al pez B sí y solo sí ~LA >= 2 * LB~). No hay reglas en cuanto a cuando un pez decide comer. Un pez puede decidir comer varios peces pequeños uno después del otro, mientras algún pez puede decidir no comerse ningún pez, aún si él puede.

Scheherazade dijo que si eres es capaz de encontrar el lago, se le permitirá pescar un pez y quedarte con todas las piedras que están en su estómago. Estás deseoso de probar tu suerte, pero antes de encabezar la gran travesía, deseas saber cuántas combinaciones diferentes de piedras puede obtener capturando un simple pez.

Escribe un programa que dada la longitud de cada pez y el tipo de piedra preciosa originalmente tragada por cada pez, encuentre el número de combinaciones diferentes de piedras que puede terminar en el estómago de cualquier pez, módulo algún número entero dado ~M~. Una combinación se define solamente por el número de piedras de cada uno de los ~K~ tipos. No hay concepto de orden entre piedras, y dos piedras cualesquiera del mismo tipo son indistinguibles.

Restricciones

~1 <= F <= 500 000~ El número original de peces en el lago.

~1 <= K <= F~ El número de tipos diferentes de piedras preciosas.

~2 <=M <= 30 000~

~1 <= LX <= 1 000 000 000~ La longitud del pez ~X~.

Entrada

Su programa debe leer de la entrada estándar los siguientes datos: Línea 1 contiene al entero ~F~, el número original de peces en el lago. Línea 2 contiene al entero ~K~, número de tipos diferentes de piedras preciosas. Los tipos de piedras preciosas están representados por enteros desde 1 hasta ~K~, inclusive. Línea 3 contiene al entero ~M~. Cada una de las siguientes ~F~ líneas describen a un pez usando 2 enteros separados por un único espacio: la longitud del pez seguida por el tipo de piedra preciosa tragada originalmente por este pez.

NOTA: Para todos los casos de prueba usados para la evaluación, está garantizado que hay al menos una piedra preciosa de cada uno de los ~K~ tipos.

Salida

Su programa debe escribir para la salida estándar una única línea conteniendo un entero entre ~0~ y ~M-1~ (inclusive): el número de combinaciones posibles de piedras preciosas módulo ~M~. Tenga en cuenta que para resolver esta tarea el valor de ~M~ no tiene otra importancia que simplificar los cálculos.

Ejemplos

Entrada

5
3
7
2 2
5 1
8 3
4 1
2 3

Salida

4

Hay 11 combinaciones posibles así que usted debe imprimir 11 módulo 7 que es 4. (Para cada combinación, listamos las piedras que esta contiene. Por ejemplo, [2,3,3] es una combinación que consiste de una piedra del tipo 2 y dos piedras del tipo 3.) Estas combinaciones pueden lograrse de las formas siguientes:

[1]: Es posible que usted capture el segundo (o el cuarto) pez antes que este sea comido por otro pez.

[1,2]: Si el segundo pez se come al primer pez, entonces este tendrá una piedra preciosa del tipo 1 (la que originalmente se había tragado) y la piedra preciosa del tipo 2 (del estómago del primer pez).

[1,2,3]: Una posible forma de alcanzar esta combinación: El cuarto pez se come al primer pez, y entonces el tercer pez se come al cuarto pez. Si usted ahora captura al tercer pez, este tendrá en su estómago una piedra preciosa de cada uno de estos tipos.

[1,2,3,3]: El cuarto se come al primero, el tercero se come al cuarto, el tercero se come al quinto, usted captura al tercero.

[1,3]: El tercero se come al cuarto, usted captura a este.

[1,3,3]: El tercero se come al quinto, el tercero se come al cuarto, usted captura a este.

[2]: Usted captura al primer pez.

[2,3]: El tercero se come al primero, usted captura a este.

[2,3,3]: El tercero se come al primero, el tercero se come al quinto, usted lo captura.

[3]: Usted captura al tercer pez.

[3,3]: El tercero se come al quinto, usted lo captura.