L’équipe de production de 1박2일 a proposé un nouveau jeu de hasard. Elle donne d’abord $K$ cailloux à un joueur, qui fait tourner une roue numérotée $N$ fois. Après chaque tour, le joueur doit rendre à l’équipe autant de cailloux que le nombre obtenu. Il gagne s’il peut fournir les cailloux nécessaires pendant les $N$ tours, et perd s’il n’en a pas assez pour effectuer un paiement demandé.

La roue porte $T$ nombres, chacun étant un entier compris entre $0$ et $T-1$, bornes incluses. Les entiers peuvent se répéter, et tous les entiers de $0$ à $T-1$ ne doivent pas nécessairement apparaître.

Étant donnés $N$, $K$, $T$ et tous les nombres de la roue, écrivez un programme qui calcule le nombre de façons dont le joueur peut gagner.

Si un même nombre apparaît plusieurs fois sur la roue, ses occurrences comptent comme des possibilités distinctes malgré leur valeur identique.

Par exemple, si la roue porte les six nombres $0$, $1$, $1$, $2$, $4$, $5$, si le joueur a six cailloux et tourne la roue deux fois, il existe $30$ façons de gagner. Si le premier nombre est $0$ ou $1$, il gagne quel que soit le suivant. Si le premier est $2$, il existe cinq possibilités, en excluant un $5$ au second tour. Si le premier est $4$, il existe quatre possibilités, et s’il est $5$, il en existe trois.

Entrée

La première ligne contient trois entiers $N$, $K$, $T$, séparés par des espaces. $N$ est le nombre de tours, $K$ le nombre initial de cailloux et $T$ le nombre d’entiers sur la roue. On a $1 \le N \le 100\,000$, $1 \le K \le 1\,000$ et $2 \le T \le 20\,000$.

Les $T$ lignes suivantes, à partir de la deuxième, contiennent chacune un entier écrit sur la roue.

Sortie

Sur la première ligne, affichez le nombre de façons dont le joueur peut gagner, modulo $42\,043$.

Exemples

Entrée 1

2 6 6
0
1
1
2
4
5

Sortie 1

30