복불복 |
---|
1박2일 제작진은 다음과 같은 새로운 복불복 게임을 제안하였다. 먼저 게임을 하는 한 사람에게 K개의 조약돌을 주고, 숫자가 적혀있는 회전판을 N번 돌리게 한다. 게임을 하는 사람은 회전판을 돌려서 나오는 숫자만큼의 조약돌을 제작진에게 되돌려 주어야 한다. 회전판을 N번 돌리는 동안 제작진에게 줄 수 있는 조약돌이 있으면 게임을 하는 사람이 이기게 되고, 제작진에게 주어야 하는 조약돌이 모자라게 되면 게임에서 지게 된다. 회전판에는 T개의 숫자가 그려지고, 그려지는 숫자는 0 이상 T-1 이하의 정수 중 하나이다. 회전판에 사용되는 정수는 중복 사용이 가능하고, 0부터 T-1 사이의 정수 모두가 다 회전판에 나타나야 하는 것은 아니다. N과 K, 그리고 T와 회전판에 그려진 모든 숫자가 주어질 때, 게임을 하는 사람이 이길 수 있는 경우의 수를 계산하는 프로그램을 작성하라. 단, 회전판에 같은 수가 여러 개 있을 때 이들 수는 값은 같지만 서로 다른 경우의 수들로 계산된다. 예를 들어, 6개의 숫자 0, 1, 1, 2, 4, 5가 그려진 회전판에서 가지고 있는 조약돌의 수가 6개이고, 회전판을 2번 돌린다면, 게임을 하는 사람이 이길 수 있는 경우의 수는 30이다. 즉, 처음 나온 정수가 0 혹은 1이면, 그 다음에 어떤 수가 나오더라도 게임을 이길 수 있으며, 2가 처음 나오는 경우에는 정수 5가 나오는 경우를 제외한 5가지 경우가 존재한다. 4가 처음 나오는 경우는 4가지 경우, 5가 처음 나오는 경우에는 3가지 경우가 존재하게 된다. |
입력 | |
---|---|
첫째 줄에 3개의 정수 N, K, T가 빈칸을 사이에 두고 주어진다. N은 회전판을 돌리는 횟수를 나타내고, K는 게임을 하는 사람에게 처음 주어지는 조약돌의 개수를 나타낸다. T는 회전판에 그려져 있는 정수들의 수이다. N은 1 이상 100,000 이하이고, K는 1 이상 1,000 이하, T는 2 이상 20,000 이하이다. 둘째 줄부터 T개의 줄에는 각 줄마다 회전판에 적혀져 있는 정수가 주어진다. |
출력 | |
---|---|
첫째 줄에 게임을 하는 사람이 이길 수 있는 경우의 수를 42,043으로 나눈 나머지 값으로 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 2 6 6 0 1 1 2 4 5 | |
출력 | 30 |