<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:
        MOD = 10**9 + 7
        n = len(num)
        all_same = len(set(num)) == 1
 
        def is_larger(is1, sz_s1, is2, sz_s2, lcp):
            """ "123" > "111", "123" > "3" """
            if sz_s1 > sz_s2:
                return True
            sz_lcp = lcp[is1][is2]
            # if same length, only compare the char next to same prefix
            if sz_s1 == sz_s2 and sz_lcp < sz_s1 and num[is1+sz_lcp] > num[is2+sz_lcp]:
                return True
            return False
        
        def get_poss(i, sz_part1, memo):
            """ if part1 as num[i..i+sz_part1] is 0, try whole num[i..n] as part1 """
            return memo[i][sz_part1] if memo[i][sz_part1] != 0 else memo[i][n-i]

        if all_same:
            lcp = None
        else:
            # lcp[i][j]: longest common prefix starting in index i and index j where i < j
            lcp = [[0 for _ in range(n+1)] for _ in range(n+1)]
            for j in range(n-1, 0, -1):
                for i in range(j-1, -1, -1):
                    if num[i] == num[j]:
                        lcp[i][j] = lcp[i+1][j+1] + 1
        
        # memo[i][sz_part1]: possibles of all sizes of part1 >= sz_part1
        memo = [[0 for _ in range(n+1)] for _ in range(n+1)] 
        for i in range(n-1, -1, -1):
            if num[i] == '0':
                continue
            # use whole num[i..n] as part1
            memo[i][n-i] = 1
            # part1's size max as size(num[i..n])/2, remaining size for part 2, skip others as impossibles
            for sz_part1 in range(math.floor((n-i)/2), 0, -1): 
                i_nx, sz_partnx = i+sz_part1, sz_part1
                # if all same number, just start with part1 size = part_next size (e.g. 111,111)
                # otherwise, do part1, part_next comparison
                if not all_same and is_larger(i, sz_part1, i_nx, sz_partnx, lcp):
                    sz_partnx += 1
                # only process when next part is within range
                if i_nx + sz_partnx-1 <= n-1:
                    memo[i][sz_part1] = (get_poss(i, sz_part1+1, memo)
                                         + get_poss(i_nx, sz_partnx, memo)) % MOD 
        return get_poss(0, 1, memo)
1182