A List Without Commas

Hard

Someone wrote several positive integers one after another but forgot the commas between them, which produced the string digits. The numbers were in non-decreasing order (each one at least as large as the one before it), and none of them started with a zero. Count how many different lists of numbers could have produced this string. A list with a single number counts too. The answer can be large, so return it modulo 10⁹ + 7.

Example 1

digits="1210" → 3

Three readings work: 1210; 1, 210; and 1, 2, 10. The split 12, 10 fails because 12 is larger than 10.

Example 2

digits="5402" → 2

5402 and 5, 402 work. 54, 02 has a leading zero, and 540, 2 is decreasing.

Example 3

digits="07" → 0

Every reading starts with a number that has a leading zero, so there are none.

Constraints

1 ≤ len(digits) ≤ 3500
digits consists of the digits 0 to 9

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming Suffix Array

Similar problems

Cheapest Build From Pieces Hard Longest Piece Seen Twice Medium Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard

Input

digits="1210"

Expected

Run checks the first 3 tests in your browser. Submit checks all 108 tests on the server, hidden ones included.