El equipo de producción de 1박2일 propuso un nuevo juego de azar. Primero entrega $K$ piedras a un jugador y le hace girar una ruleta numerada $N$ veces. Tras cada giro, el jugador debe devolver al equipo tantas piedras como indique el número obtenido. Gana si puede entregar las piedras necesarias durante los $N$ giros y pierde si no tiene suficientes para realizar algún pago.

La ruleta tiene $T$ números, cada uno de ellos un entero entre $0$ y $T-1$, ambos inclusive. Los enteros pueden repetirse y no es necesario que aparezcan todos los enteros entre $0$ y $T-1$.

Dados $N$, $K$, $T$ y todos los números de la ruleta, escribe un programa que calcule cuántas formas tiene el jugador de ganar.

Si un mismo número aparece varias veces, cada aparición se cuenta como una posibilidad distinta, aunque sus valores sean iguales.

Por ejemplo, si la ruleta tiene los seis números $0$, $1$, $1$, $2$, $4$, $5$, el jugador tiene seis piedras y gira dos veces, hay $30$ formas de ganar. Si el primer número es $0$ o $1$, gana cualquiera que sea el siguiente. Si el primero es $2$, hay cinco posibilidades, excluyendo que después salga $5$. Si el primero es $4$, hay cuatro posibilidades, y si es $5$, hay tres.

Entrada

La primera línea contiene tres enteros $N$, $K$, $T$, separados por espacios. $N$ es el número de giros, $K$ la cantidad inicial de piedras y $T$ la cantidad de enteros de la ruleta. Se cumple $1 \le N \le 100\,000$, $1 \le K \le 1\,000$ y $2 \le T \le 20\,000$.

Las siguientes $T$ líneas, a partir de la segunda, contienen cada una un entero escrito en la ruleta.

Salida

Imprime en la primera línea el número de formas de ganar, módulo $42\,043$.

Ejemplos

Entrada 1

2 6 6
0
1
1
2
4
5

Salida 1

30