A equipa de produção de 1박2일 propôs um novo jogo de azar. Primeiro, entrega $K$ pedras a um jogador e pede-lhe que faça girar uma roleta numerada $N$ vezes. Após cada giro, o jogador deve devolver à equipa tantas pedras quantas o número obtido. Ganha se conseguir entregar as pedras necessárias durante todos os $N$ giros e perde se não tiver pedras suficientes para algum pagamento.

A roleta contém $T$ números, cada um um inteiro entre $0$ e $T-1$, inclusive. Os inteiros podem repetir-se e não é necessário que todos os inteiros entre $0$ e $T-1$ apareçam.

Dados $N$, $K$, $T$ e todos os números da roleta, escreva um programa que calcule o número de maneiras de o jogador ganhar.

Se o mesmo número aparecer várias vezes na roleta, cada ocorrência conta como uma possibilidade diferente, apesar de os valores serem iguais.

Por exemplo, se a roleta tiver os seis números $0$, $1$, $1$, $2$, $4$, $5$, o jogador tiver seis pedras e girar duas vezes, há $30$ maneiras de ganhar. Se o primeiro número for $0$ ou $1$, ganha independentemente do seguinte. Se o primeiro for $2$, há cinco possibilidades, excluindo sair $5$ a seguir. Se o primeiro for $4$, há quatro possibilidades, e se for $5$, há três.

Entrada

A primeira linha contém três inteiros $N$, $K$, $T$, separados por espaços. $N$ é o número de giros, $K$ o número inicial de pedras e $T$ a quantidade de inteiros na roleta. Os limites são $1 \le N \le 100\,000$, $1 \le K \le 1\,000$ e $2 \le T \le 20\,000$.

As $T$ linhas seguintes, a partir da segunda, contêm cada uma um inteiro escrito na roleta.

Saída

Na primeira linha, imprima o número de maneiras de o jogador ganhar, módulo $42\,043$.

Exemplos

Entrada 1

2 6 6
0
1
1
2
4
5

Saída 1

30