팬 서비스
시간 제한2초메모리 제한128 MB
주어진 숫자 집합으로 만든 길이 2K 응모번호 중 앞뒤 절반의 합이 같거나 홀짝 위치의 합이 같은 경우의 수를 999983으로 나눈 나머지로 구하는 문제입니다.
문제
세계적으로 인기 있는 가수 오영식의 콘서트에서 경품 추첨을 한다. 각 관객은 길이가 2K인 티켓 번호를 가지고 있으며, 번호의 각 자리에는 주어진 숫자 중 하나가 쓰인다. 같은 숫자를 여러 자리에 사용해도 된다.
티켓 번호가 다음 두 조건 중 하나 이상을 만족하면 경품을 받을 수 있다.
- 앞의
K자리 숫자 합과 뒤의K자리 숫자 합이 같다. - 왼쪽부터 세었을 때 홀수 번째 자리의 숫자 합과 짝수 번째 자리의 숫자 합이 같다.
K와 티켓 번호에 사용할 수 있는 숫자들이 주어질 때, 경품을 받을 수 있는 서로 다른 티켓 번호의 개수를 구하라.
입력
첫째 줄에 티켓 길이의 절반인 자연수 K가 주어진다. 전체 티켓 길이는 2K이고, K <= 50이다.
둘째 줄에는 사용할 수 있는 숫자들이 공백 없이 주어진다. 각 숫자는 0 이상 9 이하이며, 같은 숫자는 두 번 나오지 않는다.
출력
경품을 받을 수 있는 티켓 번호의 개수를 999983으로 나눈 나머지를 출력한다.
힌트
K = 2이고 사용할 수 있는 숫자가 2와 1인 경우, 조건을 만족하는 티켓 번호는 1111, 1122, 1212, 1221, 2112, 2121, 2211, 2222이다.