Increasing Sequence

Time limit2sMemory limit128 MB

Summary

Split a huge digit string into pieces forming a strictly increasing sequence of numbers, breaking ties by minimizing the last piece then maximizing earlier pieces, and output the product mod 1,000,000,003.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, String, Math
Solved: No attempts yet

Problem

Jimin has one large integer with N digits.

He wants to insert spaces between digits and split it into several integers. The resulting integers must be strictly increasing from left to right. Equal values are not allowed, and an integer may start with 0.

If there is more than one valid split, choose one whose last integer is as small as possible. If there is still more than one, maximize the first integer; if still tied, maximize the second integer, and continue comparing from left to right.

Print the product of all integers in the chosen increasing sequence modulo 1,000,000,003.

Input

The first line contains one integer. Its length is at most 2500, and its first digit is not 0.

Output

Print the product of all elements in the chosen sequence modulo 1,000,000,003.

Hint

For the input 20210222, the following four splits minimize the last integer.

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

Comparing the first integer leaves the two splits that start with 20. Comparing the second integer then selects 20 210 222, because 210 is greater than 21.

Examples6

Example 1
Input
```
20210222
```
Expected output
```
932400
```
Example 2
Input
```
12345
```
Expected output
```
120
```
Example 3
Input
```
543210
```
Expected output
```
45150
```
Example 4
Input
```
1111111111
```
Expected output
```
1356531
```
Example 5
Input
```
171829294246
```
Expected output
```
385769340
```
Example 6
Input
```
3235236
```
Expected output
```
264320
```