증가 수열

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

이 정수의 자리 사이에 공백을 넣어 여러 정수로 나누려고 한다. 나누어진 정수들은 왼쪽에서 오른쪽으로 갈수록 엄격히 증가해야 한다. 같은 값은 사용할 수 없으며, 각 정수는 0으로 시작해도 된다.

가능한 나누기 방법이 여러 가지라면 마지막 정수의 값을 가장 작게 만든다. 그런 방법도 여러 가지라면 첫 번째 정수의 값을 가장 크게 하고, 그래도 같으면 두 번째 정수의 값을 가장 크게 하는 식으로 앞에서부터 차례대로 비교해 하나를 고른다.

선택된 증가 수열의 모든 원소를 곱한 뒤 1,000,000,003으로 나눈 나머지를 출력하라.

첫째 줄에 정수 하나가 주어진다. 길이는 최대 2500이고, 첫 자리는 0이 아니다.

선택된 수열의 원소를 모두 곱한 값을 1,000,000,003으로 나눈 나머지를 출력한다.

입력 20210222에서는 마지막 정수를 최소로 만드는 방법이 다음 네 가지이다.

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

첫 번째 원소를 비교하면 20으로 시작하는 두 방법만 남는다. 그다음 두 번째 원소를 비교하면 210이 21보다 크므로 선택되는 수열은 20 210 222이다.