Después que el Entrenador Pedro abandonó el futbol, el Entrenador Jorge quería unirse a la diversión. El quiere formar un equipo de futbol para sus ~N~ concursantes ~(1 \leq N \leq 2,000)~ convenientemente numerados ~1..N~. Los concursantes han estado practicando pateando los balones, y cada concursante tiene un clasificación ~R_i (1 \leq R_i \leq 100,000)~ denotando su habilidad jugando futbol. El entrenador Jorge puede elegir un equipo eligiendo uno o más de sus concursantes.

Sin embargo, debido a que el entrenador Jorge necesita ser muy selectivo cuando forme los equipos de futbol, él ha añadido una restricción adicional. Como su número favorito es ~F (1 \leq F \leq 1,000)~, él únicamente aceptará un equipo si la suma de las calificaciones de cada concursante en el equipo sea divisible exactamente por ~F~.

Ayude al entrenador Jorge ha encontrar cuántos equipos distintos él puede elegir. Ya que este número puede ser muy grande, dé la respuesta de salida módulo ~100,000,000~.

FORMATO DE ENTRADA:

• Línea 1: Dos enteros separados por espacio: ~N~ y ~F~

• Líneas 2..N+1: La línea ~i+1~ contiene un solo entero: ~R_i~

FORMATO DE LA SALIDA:

• Línea 1: Un solo entero representando el número de equipos que el entrenador puede elegir, módulo ~100,000,000~.

ENTRADA EJEMPLO

4 5
1
2
8
2

SALIDA EJEMPLO

3

DETALLES DE LA ENTRADA:

El entrenador Jorge tiene cuatro concursantes cuyas calificaciones son 1, 2, 8, y 2. El únicamente aceptará un equipo cuya suma de calificaciones sea un múltiplo de 5.

DETALLES DE LA SALIDA:

El entrenador Jorge puede armar una pareja con el concursante con calificación 8 y con cualquiera de los de calificación 2 (8 + 2 = 10), o el puede usar Los dos con calificación 2 y el de calificación 1 (2 + 2 + 1 = 5).