지민이는 길이가 N인 큰 수를 가지고 있다.</p>

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

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

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

입력 형식

첫째 줄에 수가 주어진다. 이 수의 길이는 최대 2500이다. 수는 0으로 시작하지 않는다.

출력 형식

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

예제 입력 1

20210222

예제 출력 1

932400

예제 입력 2

12345

예제 출력 2

120

예제 입력 3

543210

예제 출력 3

45150

예제 입력 4

1111111111

예제 출력 4

1356531

예제 입력 5

171829294246

예제 출력 5

385769340

예제 입력 6

3235236

예제 출력 6

264320

힌트

예제 1의 경우 마지막 원소를 최소로 한 방법은 아래와 같이 4가지가 있다.</p>

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

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