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가지 경우가 존재하게 된다.
입력 2 6 6 0 1 1 2 4 5 출력 30
출처: 2009 koi 지역 고등 4 번대회 풀이