Das Produktionsteam von 1박2일 hat ein neues Glücksspiel vorgeschlagen. Zunächst erhält ein Spieler $K$ Kieselsteine und dreht ein mit Zahlen beschriftetes Rad $N$ Mal. Nach jeder Drehung muss er dem Team so viele Steine zurückgeben, wie die erhaltene Zahl angibt. Er gewinnt, wenn er bei allen $N$ Drehungen die erforderlichen Steine abgeben kann, und verliert, wenn seine Steine für eine erforderliche Zahlung nicht ausreichen.

Auf dem Rad stehen $T$ Zahlen, jeweils ganze Zahlen von $0$ bis einschließlich $T-1$. Zahlen dürfen mehrfach vorkommen, und es müssen nicht alle ganzen Zahlen von $0$ bis $T-1$ auf dem Rad stehen.

Schreibe ein Programm, das für gegebene $N$, $K$, $T$ und alle Zahlen auf dem Rad die Anzahl der Möglichkeiten berechnet, bei denen der Spieler gewinnt.

Wenn dieselbe Zahl mehrfach auf dem Rad steht, zählen diese Vorkommen trotz ihres gleichen Werts als verschiedene Möglichkeiten.

Stehen beispielsweise die sechs Zahlen $0$, $1$, $1$, $2$, $4$, $5$ auf dem Rad, hat der Spieler sechs Steine und dreht zweimal, so gibt es $30$ Gewinnmöglichkeiten. Ist die erste Zahl $0$ oder $1$, gewinnt er unabhängig von der nächsten Zahl. Ist die erste Zahl $2$, gibt es fünf Möglichkeiten, wobei eine anschließende $5$ ausgeschlossen ist. Bei einer ersten $4$ gibt es vier Möglichkeiten und bei einer ersten $5$ drei.

Eingabe

Die erste Zeile enthält drei durch Leerzeichen getrennte ganze Zahlen $N$, $K$, $T$. Dabei ist $N$ die Anzahl der Drehungen, $K$ die anfängliche Anzahl der Steine und $T$ die Anzahl der Zahlen auf dem Rad. Es gilt $1 \le N \le 100\,000$, $1 \le K \le 1\,000$ und $2 \le T \le 20\,000$.

Die folgenden $T$ Zeilen enthalten ab der zweiten Zeile jeweils eine auf dem Rad stehende ganze Zahl.

Ausgabe

Gib in der ersten Zeile die Anzahl der Gewinnmöglichkeiten modulo $42\,043$ aus.

Beispiele

Eingabe 1

2 6 6
0
1
1
2
4
5

Ausgabe 1

30