Pebble Game of Chance

A player starts with K pebbles. A wheel has T positions, and each position contains one integer from 0 to T-1. The same integer may appear on several positions, and not every integer from 0 to T-1 has to appear.

The player spins the wheel N times. After each spin, the player must return as many pebbles as the integer shown on the wheel. If the player can pay the required number of pebbles after every one of the N spins, the player wins. If the player ever does not have enough pebbles, the player loses.

Given N, K, T, and all T numbers on the wheel, count the number of distinct outcome sequences in which the player wins. If the same integer appears on multiple positions, those positions are counted as different outcomes even though their values are equal.

For example, suppose the wheel contains 0, 1, 1, 2, 4, 5, the player starts with 6 pebbles, and the wheel is spun 2 times. The number of winning outcome sequences is 30. If the first number is 0 or 1, any second number still wins. If the first number is 2, all second numbers except 5 work, giving 5 cases. If the first number is 4, there are 4 cases; if it is 5, there are 3 cases.

The first line contains three integers N, K, and T separated by spaces. N is the number of spins, K is the initial number of pebbles, and T is the number of positions on the wheel.

• 1 <= N <= 100,000
• 1 <= K <= 1,000
• 2 <= T <= 20,000

Each of the next T lines contains one integer written on one position of the wheel. Each integer is between 0 and T-1, inclusive.

Print one line containing the number of winning outcome sequences modulo 42,043.