Ekipa programu 1박2일 zaproponowała nową grę losową. Gracz otrzymuje najpierw $K$ kamyków i obraca kołem z liczbami $N$ razy. Po każdym obrocie musi oddać ekipie tyle kamyków, ile wynosi wylosowana liczba. Gracz wygrywa, jeśli może oddać wymaganą liczbę kamyków przy wszystkich $N$ obrotach, a przegrywa, gdy zabraknie mu kamyków na wymaganą zapłatę.

Na kole zapisano $T$ liczb całkowitych z przedziału od $0$ do $T-1$ włącznie. Liczby mogą się powtarzać i nie każda liczba od $0$ do $T-1$ musi występować na kole.

Mając dane $N$, $K$, $T$ i wszystkie liczby na kole, napisz program obliczający liczbę sposobów, na jakie gracz może wygrać.

Jeśli ta sama liczba występuje na kole wielokrotnie, jej wystąpienia liczy się jako różne możliwości, mimo że mają tę samą wartość.

Na przykład, gdy na kole są liczby $0$, $1$, $1$, $2$, $4$, $5$, gracz ma sześć kamyków i obraca kołem dwa razy, istnieje $30$ sposobów wygranej. Jeśli pierwsza liczba to $0$ lub $1$, gracz wygra niezależnie od drugiej. Jeśli pierwsza liczba to $2$, jest pięć możliwości, z wyłączeniem drugiej liczby $5$. Dla pierwszej liczby $4$ są cztery możliwości, a dla $5$ — trzy.

Wejście

Pierwszy wiersz zawiera trzy liczby całkowite $N$, $K$, $T$, oddzielone spacjami. $N$ oznacza liczbę obrotów, $K$ początkową liczbę kamyków gracza, a $T$ liczbę liczb na kole. Zachodzi $1 \le N \le 100\,000$, $1 \le K \le 1\,000$ oraz $2 \le T \le 20\,000$.

W kolejnych $T$ wierszach, począwszy od drugiego, podano po jednej liczbie całkowitej zapisanej na kole.

Wyjście

W pierwszym wierszu wypisz liczbę sposobów wygranej gracza modulo $42\,043$.

Przykład

Wejście 1

2 6 6
0
1
1
2
4
5

Wyjście 1

30