1박2일 の制作陣は、新しい運試しゲームを提案しました。まず、プレイヤーに $K$ 個の小石を渡し、数字の書かれたルーレットを $N$ 回回させます。プレイヤーは毎回、出た数字と同じ個数の小石を制作陣に返さなければなりません。$N$ 回すべてで必要な小石を渡せれば勝ちとなり、渡すべき小石が足りなくなると負けとなります。

ルーレットには $T$ 個の数字が書かれ、それぞれは $0$ 以上 $T-1$ 以下の整数です。同じ整数を重複して使用でき、$0$ から $T-1$ までのすべての整数が現れる必要はありません。

$N$、$K$、$T$ およびルーレットに書かれたすべての数字が与えられたとき、プレイヤーが勝てる場合の数を計算するプログラムを作成してください。

ルーレットに同じ数が複数ある場合、値が等しくても、それぞれを異なる場合として数えます。

例えば、ルーレットに六つの数 $0$、$1$、$1$、$2$、$4$、$5$ が書かれ、小石を六つ持っていて、ルーレットを二回回す場合、勝てる場合の数は $30$ です。最初に $0$ または $1$ が出れば、次にどの数が出ても勝てます。最初に $2$ が出る場合、次に $5$ が出る場合を除く五通りがあります。最初に $4$ が出る場合は四通り、$5$ が出る場合は三通りあります。

入力

1 行目に、空白で区切られた三つの整数 $N$、$K$、$T$ が与えられます。$N$ は回す回数、$K$ は最初に渡される小石の個数、$T$ はルーレットに書かれた整数の個数です。$1 \le N \le 100\,000$、$1 \le K \le 1\,000$、$2 \le T \le 20\,000$ を満たします。

2 行目からの $T$ 行には、各行にルーレットに書かれた整数が一つずつ与えられます。

出力

1 行目に、プレイヤーが勝てる場合の数を $42\,043$ で割った余りを出力してください。

入出力例

入力 1

2 6 6
0
1
1
2
4
5

出力 1

30