2 * K자리로 이루어진 숫자로 만들어진 티켓 번호가 있다.

이러한 티켓번호가 "멋진 티켓"이 되기 위해선 적어도 아래의 조건 중 하나를 만족시켜야 한다.

* 첫 번째 K개의 자리의 합이 마지막 K개의 합과 같다. * 모든 홀수 자리의 합이 모든 짝수 자리의 합과 같다.

K와 사용가능한 한자리의 숫자들이 주어졌을 때,

2 * K 자리수로 만들어지는 "멋진 티켓"을 만들 수 있는 모든 경우의 수를 알아보는 프로그램을 작성하라.

숫자가 너무 커질 수 있기 때문에, 999983으로 나눈 나머지를 출력하면 된다.

티켓 번호의 맨 앞의 수가 0이 될 수도 있다.

멋진 티켓번호 timer 1s memory 256MB

멋진 티켓번호 1s 256MB