시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

지민이는 길이가 N인 큰 수를 가지고 있다.

지민이는 이 수에 공백을 적절히 넣어서 오름차순 순열로 만들려고 한다. (같은 수는 안 되고, 0으로 시작하는 수도 된다)

만약 수를 나누는 방법이 여러 가지가 있으면, 가장 마지막 수를 최소로 하려고 한다. 그래도 여러 가지 방법이 있을 때에는, 첫 번째 원소를 최대로, 그래도 같으면, 두 번째 원소를 최대로 하려고 한다. 이렇게 계속 ...

지민이가 구한 오름차순 수열의 모든 원소를 곱해서 1,000,000,003으로 나눈 값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 수가 주어진다. 이 수의 길이는 최대 2500이다.

출력

첫째 줄에 곱을 1,000,000,003으로 나눈 값을 출력 한다.

예제 입력

20210222

예제 출력

932400

힌트

마지막 원소를 최소로 한 방법은 아래와 같이 4가지가 있다.

  • 2 021 0222
  • 2 0210 222
  • 20 21 0222
  • 20 210 222

일단 마지막 두 수열 중에 정답이 있다. 그 이유는 첫 번째 원소인 2와 20중 큰 것이 20이기 때문이다. 그리고 두 번째 원소를 보면 네 번째 방법이 가장 크기 때문에 정답은 네 번째 방법이 된다.

출처