조약돌 복불복

게임 참가자는 처음에 K개의 조약돌을 받는다. 회전판에는 T개의 칸이 있고, 각 칸에는 0 이상 T-1 이하의 정수가 하나 적혀 있다. 같은 정수가 여러 칸에 적혀 있을 수 있으며, 0부터 T-1까지의 모든 정수가 반드시 등장할 필요는 없다.

참가자는 회전판을 N번 돌린다. 매번 나온 정수만큼 조약돌을 제작진에게 돌려주어야 한다. N번의 회전이 끝날 때까지 매번 필요한 만큼의 조약돌을 줄 수 있으면 참가자는 이기고, 어느 순간이라도 조약돌이 부족하면 진다.

N, K, T와 회전판의 T개 숫자가 주어질 때, 참가자가 이길 수 있는 서로 다른 결과열의 수를 구하라. 같은 숫자가 여러 칸에 적혀 있으면 값은 같아도 서로 다른 결과로 센다.

예를 들어, 회전판의 숫자가 0, 1, 1, 2, 4, 5이고 처음 조약돌이 6개이며 회전판을 2번 돌린다고 하자. 가능한 결과열 중 참가자가 이기는 경우의 수는 30이다. 첫 번째 숫자가 0 또는 1이면 두 번째 숫자가 무엇이든 이길 수 있다. 첫 번째 숫자가 2이면 두 번째 숫자가 5인 경우를 제외한 5가지가 가능하고, 첫 번째 숫자가 4이면 4가지, 첫 번째 숫자가 5이면 3가지가 가능하다.

첫째 줄에 정수 N, K, T가 공백으로 구분되어 주어진다. N은 회전판을 돌리는 횟수, K는 처음 받는 조약돌의 개수, T는 회전판에 적힌 숫자의 개수이다.

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

다음 T개 줄에는 각 줄마다 회전판의 한 칸에 적힌 정수가 하나씩 주어진다. 각 정수는 0 이상 T-1 이하이다.

첫째 줄에 참가자가 이길 수 있는 경우의 수를 42,043으로 나눈 나머지를 출력한다.