<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>

MOD = int(1e9+7)

class Solution:
    def numberOfCombinations(self, num: str) -> int:
        """
        If previous number is num[i:j], in order to count number of combs in num[j:],
        then count(i, j) = sum(count(j, k) for k that num[j:k] >= num[i:j] and without leading zero).
        
        Fix j, and increment i. Decrement k to match i.
        Goal: sum count(0, j) for all 1 <= j <= n.
        Initial: When j == n, count = 1 if no leading zeros, or else 0.
        """
        n = len(num)
        counts = [[0] * (n+1) for _ in range(n)]
        # If all characters in num are the same, set this flag to save time in partial_compare
        all_same_flag = True if num.count(num[0]) == len(num) else False
        for i in range(n):
            counts[i][n] = 1 if num[i] != '0' else 0
        
        @cache
        def partial_compare(i, j) -> int:
            """Return
			0: num[i:j] == num[j:2*j-i]
			>0: num[i:j] > num[j:2*j-i], and the value is the first position (1-indexed) where they're different
			<0: num[i:j] < num[j:2*j-i], and the absolute value is the first position (1-indexed) where they're different
			"""
            if i == j or all_same_flag:
                return 0
            elif num[i] != num[j]:
                return i+1 if num[i] > num[j] else -(i+1)
            elif 2*j - i == n or 2*j - i == n-1:
                for k in range(j-i):
                    if num[i+k] != num[j+k]:
                        return i+k if num[i+k] > num[j+k] else -(i+k+1)
                return 0
            else:
                idx = partial_compare(i+1, j+1)
                return 0 if idx == 0 or abs(idx)-1 >= j else idx
            
        ans = counts[0][n]
        for j in range(n-1, 0, -1):
            k, total = n, 0
            for i in range(j):
                if num[i] != '0':
                    while k-j > j-i or (k-j == j-i and partial_compare(i, j) <= 0):
                        total = (total + counts[j][k]) % MOD
                        k -= 1
                    counts[i][j] = total
            ans = (ans + counts[0][j]) % MOD
            # No longer used
            del counts[j]
        return ans
2481