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