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$ 時有三種情況。

輸入格式

第一行給出三個以空格分隔的整數 $N$、$K$、$T$。$N$ 表示轉動轉盤的次數，$K$ 表示玩家初始獲得的石子數，$T$ 表示轉盤上整數的個數。滿足 $1 \le N \le 100\,000$、$1 \le K \le 1\,000$、$2 \le T \le 20\,000$。

從第二行起的 $T$ 行，每行給出一個寫在轉盤上的整數。

輸出格式

第一行輸出玩家能夠獲勝的情況數對 $42\,043$ 取模後的結果。

範例

輸入格式 1

2 6 6
0
1
1
2
4
5

輸出格式 1

30