팬 서비스

세계적으로 인기 있는 가수 오영식의 콘서트에서 경품 추첨을 한다. 각 관객은 길이가 2K인 티켓 번호를 가지고 있으며, 번호의 각 자리에는 주어진 숫자 중 하나가 쓰인다. 같은 숫자를 여러 자리에 사용해도 된다.

티켓 번호가 다음 두 조건 중 하나 이상을 만족하면 경품을 받을 수 있다.

1. 앞의 K자리 숫자 합과 뒤의 K자리 숫자 합이 같다.
2. 왼쪽부터 세었을 때 홀수 번째 자리의 숫자 합과 짝수 번째 자리의 숫자 합이 같다.

K와 티켓 번호에 사용할 수 있는 숫자들이 주어질 때, 경품을 받을 수 있는 서로 다른 티켓 번호의 개수를 구하라.

첫째 줄에 티켓 길이의 절반인 자연수 K가 주어진다. 전체 티켓 길이는 2K이고, K <= 50이다.

둘째 줄에는 사용할 수 있는 숫자들이 공백 없이 주어진다. 각 숫자는 0 이상 9 이하이며, 같은 숫자는 두 번 나오지 않는다.

경품을 받을 수 있는 티켓 번호의 개수를 999983으로 나눈 나머지를 출력한다.

K = 2이고 사용할 수 있는 숫자가 2와 1인 경우, 조건을 만족하는 티켓 번호는 1111, 1122, 1212, 1221, 2112, 2121, 2211, 2222이다.