<p>We call a positive integer <strong>special</strong> if all of its digits are <strong>distinct</strong>.</p>

<p>Given a <strong>positive</strong> integer <code>n</code>, return <em>the number of special integers that belong to the interval </em><code>[1, n]</code>.</p>

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

<pre>
<strong>Input:</strong> n = 20
<strong>Output:</strong> 19
<strong>Explanation:</strong> All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.
</pre>

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

<pre>
<strong>Input:</strong> n = 5
<strong>Output:</strong> 5
<strong>Explanation:</strong> All the integers from 1 to 5 are special.
</pre>

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

<pre>
<strong>Input:</strong> n = 135
<strong>Output:</strong> 110
<strong>Explanation:</strong> There are 110 integers from 1 to 135 that are special.
Some of the integers that are not special are: 22, 114, and 131.</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 10<sup>9</sup></code></li>
</ul>

from functools import cache
class Solution:
    def countSpecialNumbers(self, num: int) -> int:
        # 3 7 1
        # _ _ _

        num = str(num)
        n = len(num)
        @cache
        def DP(i, bound, mask, zeros):
            if i == n:
                return 1 
            
            mx = 10 if not bound else (int(num[i]) + 1)
            m = 1 
            res = 0
            for x in range(mx):
                if (m & mask) != 0: 
                    m <<= 1
                    continue 
                if x == 0 and zeros == i:
                    res += DP(i+1, False, mask, zeros+1)
                elif bound and x == mx-1:
                    res += DP(i+1, True, mask|m, zeros)
                else:
                    res += DP(i+1, False, mask|m, zeros)
                m <<= 1

            return res 
        
        return DP(0,True,0,0) - 1





206