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가지 경우가 존재하게 된다.

복불복 timer 1s memory 128MB

복불복 1s 128MB