<p>Given an array of integers <code>nums</code> and an integer <code>k</code>, return the number of <span data-keyword="subarray-nonempty">subarrays</span> of <code>nums</code> where the bitwise <code>AND</code> of the elements of the subarray equals <code>k</code>.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,1], k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<p>All subarrays contain only 1&#39;s.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,2], k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>Subarrays having an <code>AND</code> value of 1 are: <code>[<u><strong>1</strong></u>,1,2]</code>, <code>[1,<u><strong>1</strong></u>,2]</code>, <code>[<u><strong>1,1</strong></u>,2]</code>.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3], k = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>Subarrays having an <code>AND</code> value of 2 are: <code>[1,<b><u>2</u></b>,3]</code>, <code>[1,<u><strong>2,3</strong></u>]</code>.</p>
</div>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i], k &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        breaker_indices = deque()
        for index in range(len(nums)):
            if nums[index] & k < k:
                breaker_indices.append(index)
        set_breaker_indices = set(breaker_indices)
        breaker_indices.append(len(nums))
        
        nums_without_bit = defaultdict(deque)
        for index in range(len(nums)):
            if index in set_breaker_indices:
                continue

            for bit in range(32):
                b = 1 << bit
                if nums[index] & b != b:
                    nums_without_bit[b].append(index)
        
        k_not_bits = []
        for bit in range(32):
            b = 1 << bit
            if k & b != b:
                k_not_bits.append(b)
        
        ret = 0
        for index in range(len(nums)):
            if index in set_breaker_indices:
                continue
            
            while breaker_indices[0] < index:
                breaker_indices.popleft()
            next_breaker_index = breaker_indices[0]
            
            if nums[index] == k:
                n_valid = next_breaker_index - index
                ret += n_valid
            else:
                last_idx = index
                val = nums[index]
                for extra_bit in k_not_bits:
                    if extra_bit & val != extra_bit:
                        continue
                    d = nums_without_bit[extra_bit]
                    while len(d) > 0 and d[0] < index:
                        d.popleft()
                    if len(d) == 0:
                        break
                    val &= nums[d[0]]
                    last_idx = max(last_idx, d[0])
                    
                if val == k and next_breaker_index > last_idx:
                    n_valid = next_breaker_index - last_idx
                    ret += n_valid

        return ret
2264