시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB161565338.971%

문제

세계적인 인기 스타 오영식의 콘서트가 열리고 있다. 오영식은 중간에 팬 서비스로 경품 추첨 행사를 열려고 한다.

티켓 번호를 이용해서 경품을 주려고 한다.

티켓 번호는 2K자리이고, 경품을 받을 조건은 다음과 같으며, 둘 중 하나 이상을 만족해야 한다.

  1. 처음 K자리의 합은 뒤 K자리의 합과 같다.
  2. 짝수자리의 합은 홀수자리의 합과 같다.

티켓의 자리수와, 티켓에 등장하는 숫자가 주어졌을 때, 경품을 받을 수 있는 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 티켓의 길이의 절반 K가 주어진다. 즉, 티켓의 길이는 2K이다. K는 50보다 작거나 같은 자연수이다. 둘째 줄에 티켓에 등장하는 숫자가 주어진다. 티켓에 등장하는 숫자는 공백없이 주어지며 중복되지 않는다. 주어지는 숫자는 0보다 크거나 같고 9보다 작거나 같다.

출력

경품을 받을 수 있는 티켓의 개수를 999,983으로 나눈 나머지를 첫째 줄에 출력한다.

예제 입력 1

2
21

예제 출력 1

8

예제 입력 2

1
0123456789

예제 출력 2

10

예제 입력 3

2
0123456789

예제 출력 3

1240

예제 입력 4

10
731

예제 출력 4

207444

예제 입력 5

50
0123456789

예제 출력 5

367584

힌트

예제 1: 1111, 1122, 1212, 1221, 2112, 2121, 2211, 2222

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: chogahui05
  • 잘못된 조건을 찾은 사람: restart