The production team of 1박2일 has proposed a new game of chance. First, a player receives $K$ pebbles and spins a numbered wheel $N$ times. After each spin, the player must return as many pebbles to the production team as the number obtained. The player wins if they can pay the required pebbles throughout all $N$ spins, and loses if they do not have enough pebbles to make a required payment.

The wheel has $T$ numbers, each an integer from $0$ to $T-1$, inclusive. Integers may be repeated, and not every integer from $0$ to $T-1$ needs to appear.

Given $N$, $K$, $T$, and every number on the wheel, write a program that computes the number of ways the player can win.

If the same number appears multiple times on the wheel, these occurrences count as distinct possibilities even though their values are equal.

For example, suppose the wheel has six numbers $0$, $1$, $1$, $2$, $4$, $5$, the player has six pebbles, and the wheel is spun twice. There are $30$ ways to win. If the first number is $0$ or $1$, the player wins regardless of the next number. If the first number is $2$, there are five possibilities, excluding a subsequent $5$. There are four possibilities when the first number is $4$, and three when it is $5$.

Input

The first line contains three space-separated integers $N$, $K$, and $T$. Here, $N$ is the number of spins, $K$ is the initial number of pebbles, and $T$ is the number of integers on the wheel. The bounds are $1 \le N \le 100\,000$, $1 \le K \le 1\,000$, and $2 \le T \le 20\,000$.

The next $T$ lines, starting with the second line, each contain one integer written on the wheel.

Output

On the first line, print the number of ways the player can win, modulo $42\,043$.

Examples

Input 1

2 6 6
0
1
1
2
4
5

Output 1

30