문제
2 * K자리로 이루어진 숫자로 만들어진 티켓 번호가 있다.
이러한 티켓번호가 "멋진 티켓"이 되기 위해선 적어도 아래의 조건 중 하나를 만족시켜야 한다.
* 첫 번째 K개의 자리의 합이 마지막 K개의 합과 같다. * 모든 홀수 자리의 합이 모든 짝수 자리의 합과 같다.
K와 사용가능한 한자리의 숫자들이 주어졌을 때,
2 * K 자리수로 만들어지는 "멋진 티켓"을 만들 수 있는 모든 경우의 수를 알아보는 프로그램을 작성하라.
숫자가 너무 커질 수 있기 때문에, 999983으로 나눈 나머지를 출력하면 된다.
티켓 번호의 맨 앞의 수가 0이 될 수도 있다.
입력
첫 번째 줄에는 테스트 케이스의 개수 T(T≤100)이 입력된다. 테스트 케이스의 첫 번째 줄에는 K가 입력되며, 이는 50이하의 양의 정수이다. 그 다음 줄에는 하나의 문자열이 입력되는데, 이 문자는 사용 가능한 숫자들을 뜻한다. 하나의 숫자가 여러 번 나오는 경우는 없다.
출력
각각의 테스트 케이스에 대해 입력에 대해 만들 수 있는 2 * K 길이의 "멋진 티켓"의 가지수를 아래의 조건에 맞게 출력한다.
예제
2
1
0123456789
2
21
10
8
힌트
출처
online contest
로그인해야 코드를 작성할 수 있어요.