<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 bit_and(self, l, r, sp, p):
        if l >= r:
            return 0
        
        j = p[r - l - 1]
        result = sp[l][j] & sp[r - 2**j][j]
        return result        
        

    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        p = [int(math.log(i)/math.log(2)) for i in range(1, n+1)]
        sp = [[2**35 - 1 for j in range(17)] for i in range(n)]
        
        for i in range(n):
            sp[i][0] = nums[i]

        for j in range(1, 17):    
            for i in range(n):
                if i + 2**j - 1 < n:
                    sp[i][j] = sp[i][j - 1] & sp[i + 2**(j - 1)][j - 1]
                else:
                    break

        result = 0
        for start in range(n):
            if(nums[start] < k or self.bit_and(start, n, sp, p) > k):
                continue

            lower = start - 1
            upper = n
            while(upper - lower > 1):
                middle = int((lower+upper)/2)
                if self.bit_and(start, middle + 1, sp, p) > k:
                    lower = middle
                else:
                    upper = middle
            
            m1 = lower + 1

            lower = start
            upper = n
            while(upper - lower > 1):
                middle = int((lower+upper)/2)
                if self.bit_and(start, middle + 1, sp, p) >= k:
                    lower = middle
                else:
                    upper = middle
            m2 = lower
            result += m2 - m1 + 1

        return result
46600