시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 101 30 28 31.818%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력

2
21

예제 출력

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
  • 잘못된 조건을 찾은 사람: restart