<p>You are given positive integers <code>low</code>, <code>high</code>, and <code>k</code>.</p>

<p>A number is <strong>beautiful</strong> if it meets both of the following conditions:</p>

<ul>
	<li>The count of even digits in the number is equal to the count of odd digits.</li>
	<li>The number is divisible by <code>k</code>.</li>
</ul>

<p>Return <em>the number of beautiful integers in the range</em> <code>[low, high]</code>.</p>

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

<pre>
<strong>Input:</strong> low = 10, high = 20, k = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are 2 beautiful integers in the given range: [12,18]. 
- 12 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
- 18 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
Additionally we can see that:
- 16 is not beautiful because it is not divisible by k = 3.
- 15 is not beautiful because it does not contain equal counts even and odd digits.
It can be shown that there are only 2 beautiful integers in the given range.
</pre>

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

<pre>
<strong>Input:</strong> low = 1, high = 10, k = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong> There is 1 beautiful integer in the given range: [10].
- 10 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 1.
It can be shown that there is only 1 beautiful integer in the given range.
</pre>

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

<pre>
<strong>Input:</strong> low = 5, high = 5, k = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are 0 beautiful integers in the given range.
- 5 is not beautiful because it is not divisible by k = 2 and it does not contain equal even and odd digits.
</pre>

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

<ul>
	<li><code>0 &lt; low &lt;= high &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt; k &lt;= 20</code></li>
</ul>

class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
        # standard digit dp
        @lru_cache(None)
        def FormNum(s: str, idx: int, restriction: bool, diff: int, residue: int, shouldCountZero: int):
            if idx == len(s):
                if residue == 0 and diff == 0:
                    return 1
                else:
                    return 0
            
            ans = 0
            if restriction:
                # try all options till max allowed digit
                maxDigit = int(s[idx])
                newRestriction = False

                for i in range(0, maxDigit + 1):
                    newResidue = (residue * 10 + i) % k
                    newDiff = diff
                    # we don't need to restrict later digits if we decide to put a digit smaller than max allowed
                    if i == maxDigit:
                        newRestriction = True
                    # even -1, odd +1
                    if i == 0 and shouldCountZero == 1:
                        newDiff -= 1
                    elif i & 1:
                        newDiff += 1
                        shouldCountZero = 1
                    elif i != 0:
                        newDiff -= 1
                        shouldCountZero = 1
                    
                    ans += FormNum(s, idx + 1, newRestriction, newDiff, newResidue, shouldCountZero)
            else:
                # we can put whatever digit we want
                for i in range(0, 10):
                    newResidue = (residue * 10 + i) % k
                    newDiff = diff

                    if i == 0 and shouldCountZero == 1:
                        newDiff -= 1
                    elif i & 1:
                        newDiff += 1
                        shouldCountZero = 1
                    elif i != 0:
                        newDiff -= 1
                        shouldCountZero = 1

                    ans += FormNum(s, idx + 1, False, newDiff, newResidue, shouldCountZero)
            
            return ans
        
        ans1 = FormNum(str(high), 0, True, 0, 0, 0)
        ans2 = FormNum(str(low - 1), 0, True, 0, 0, 0)
        return ans1 - ans2
                

                
                    
18400