Increasing Sequence

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.

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

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

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.