<p>You wrote down many <strong>positive</strong> integers in a string called <code>num</code>. However, you realized that you forgot to add commas to seperate the different numbers. You remember that the list of integers was <strong>non-decreasing</strong> and that <strong>no</strong> integer had leading zeros.</p>

<p>Return <em>the <strong>number of possible lists of integers</strong> that you could have written down to get the string </em><code>num</code>. Since the answer may be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;327&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> You could have written down the numbers:
3, 27
327
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;094&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> No numbers can have leading zeros and all numbers must be positive.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;0&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> No numbers can have leading zeros and all numbers must be positive.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 3500</code></li>
	<li><code>num</code> consists of digits <code>&#39;0&#39;</code> through <code>&#39;9&#39;</code>.</li>
</ul>

class Solution:
    def numberOfCombinations(self, num: str) -> int:
        N = len(num)
        BIG = 10**9+7
        if num[0] == '0': return 0

        lcp = [[0]*(N+1) for _ in range(N+1)]
        for i in range(N-1, -1, -1):
            for j in range(N-1, -1, -1):
                if num[i] == num[j]:
                    lcp[i][j] = 1 + lcp[i+1][j+1]

        # and so now we implement, i needs i' > i so we fill in reverse order
        ways = [[0]*N for _ in range(N)]
        ways.append([1]*N) # ways[N][p] == 1 for all p
        for i in range(N-1, 0, -1): # i==0 is a special case; no prefix
            if num[i] == '0': continue

            # from above, each ways[i][p] reuses most of ways[i][p' < p]
            #    there's the sum of ways to parse longer numbers, i.e. i' > i+i-p
            #    and maybe the way to parse i-p digits too
            #
            # the max p is i-1 b/c we parse at least one digit
            # the min p is 0
            #    FIXED: not really, because if we parsed p:i before then we
            #           need to parse at least i-p digits for the next number
            #           if i+i-p > N though this is impossible
            #           therefore we need 2*i-p <= N, i.e. p >= 2*i-N
            #           p >= 0 also must hold
            #
            # suppose the first p is p*
            # then longer_ways starts with ways to parse more than i-p* digits,
            # aka we can parse i-p*+1, i-p*+2, etc.
            #  which is ways[2*i-p*+1][i], ways[2*i-p*+2][i], .. ways[N][i]
            min_p = max(0, 2*i-N)
            longer_ways = sum(ways[j][i] for j in range(i+i-min_p+1, N+1))
            for p in range(max(2*i-N, 0), i):
                ways[i][p] = longer_ways # ways to parse more than i-p digits from here
                
                l = lcp[i][p]
                if l >= i-p or num[i+l] > num[p+l]: # O(1) form of num[i:i+i-p] >= num[p:i]
                    # i:i+(i-p) >= p:i so we can parse an i-p digit number here
                    ways[i][p] += ways[i+i-p][i]
                    ways[i][p] %= BIG

                # for next p, aka one fewer digit we parsed before i,
                # we can parse i-p digits for sure b/c it will be one more digit
                # (see above)
                longer_ways += ways[i+i-p][i]
                longer_ways %= BIG

        # Final pass: from top-down version, starting at index i=0 we can parse
        # any number of digits:
        #   1: ways[1][0]
        #   2: ways[2][0]
        #   etc.

        return sum(ways[i][0] for i in range(1, N+1)) % BIG


        
2293