<p>The <strong>powerful array</strong> of a non-negative integer <code>x</code> is defined as the shortest sorted array of powers of two that sum up to <code>x</code>. The table below illustrates examples of how the <strong>powerful array</strong> is determined. It can be proven that the powerful array of <code>x</code> is unique.</p>

<table border="1">
	<tbody>
		<tr>
			<th>num</th>
			<th>Binary Representation</th>
			<th>powerful array</th>
		</tr>
		<tr>
			<td>1</td>
			<td>0000<u>1</u></td>
			<td>[1]</td>
		</tr>
		<tr>
			<td>8</td>
			<td>0<u>1</u>000</td>
			<td>[8]</td>
		</tr>
		<tr>
			<td>10</td>
			<td>0<u>1</u>0<u>1</u>0</td>
			<td>[2, 8]</td>
		</tr>
		<tr>
			<td>13</td>
			<td>0<u>11</u>0<u>1</u></td>
			<td>[1, 4, 8]</td>
		</tr>
		<tr>
			<td>23</td>
			<td><u>1</u>0<u>111</u></td>
			<td>[1, 2, 4, 16]</td>
		</tr>
	</tbody>
</table>

<p>The array <code>big_nums</code> is created by concatenating the <strong>powerful arrays</strong> for every positive integer <code>i</code> in ascending order: 1, 2, 3, and so on. Thus, <code>big_nums</code> begins as <code>[<u>1</u>, <u>2</u>, <u>1, 2</u>, <u>4</u>, <u>1, 4</u>, <u>2, 4</u>, <u>1, 2, 4</u>, <u>8</u>, ...]</code>.</p>

<p>You are given a 2D integer matrix <code>queries</code>, where for <code>queries[i] = [from<sub>i</sub>, to<sub>i</sub>, mod<sub>i</sub>]</code> you should calculate <code>(big_nums[from<sub>i</sub>] * big_nums[from<sub>i</sub> + 1] * ... * big_nums[to<sub>i</sub>]) % mod<sub>i</sub></code><!-- notionvc: a71131cc-7b52-4786-9a4b-660d6d864f89 -->.</p>

<p>Return an integer array <code>answer</code> such that <code>answer[i]</code> is the answer to the <code>i<sup>th</sup></code> query.</p>

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

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

<p><strong>Output:</strong> <span class="example-io">[4]</span></p>

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

<p>There is one query.</p>

<p><code>big_nums[1..3] = [2,1,2]</code>. The product of them is 4. The result is <code>4 % 7 = 4.</code></p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">queries = [[2,5,3],[7,7,4]]</span></p>

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

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

<p>There are two queries.</p>

<p>First query: <code>big_nums[2..5] = [1,2,4,1]</code>. The product of them is 8. The result is <code>8 % 3 = 2</code>.</p>

<p>Second query: <code>big_nums[7] = 2</code>. The result is <code>2 % 4 = 2</code>.</p>
</div>

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

<ul>
	<li><code>1 &lt;= queries.length &lt;= 500</code></li>
	<li><code>queries[i].length == 3</code></li>
	<li><code>0 &lt;= queries[i][0] &lt;= queries[i][1] &lt;= 10<sup>15</sup></code></li>
	<li><code>1 &lt;= queries[i][2] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def arr_i(self,x):
        num_1 = bin(x).count('1')
        num_pows = 0
        for bit in range(64):
            if not (1<<bit)&x:
                continue
            num_1 -= 1
            num_pows += num_1*(1<<bit) + bit*(1<<max(0,bit-1))            
        return num_pows

    def binsearch(self,lo,hi,x):
        while lo <= hi:
            mid = (lo+hi)>>1
            i = self.arr_i(mid)
            j = i + bin(mid).count('1')
            if j<=x:
                lo = mid+1
            elif i>x:
                hi = mid-1
            else:
                return (mid, i)
        print('index not found, increase hi')
        return -1
    
    def compute_exp(self,x):
        prefix = sum([bit if (1<<bit)&x else 0 for bit in range(64)])
        exp = 0
        for bit in range(64):
            if not (1<<bit)&x:
                continue
            prefix -= bit
            a = prefix*(1<<bit)
            b = ((bit*(bit-1))>>1) * (1<<max(0,bit-1))
            exp += a+b
        return exp
    
    def pows_till_i(self,x, i):
        exp = 0
        n = 0
        for bit in range(64):
            if n > i:
                break
            if (1<<bit)&x:
                exp += bit
                n+=1
        return exp

    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
        answer = []
        for (frm, to, mod) in queries:
            x,i = self.binsearch(1,1<<64,to)
            exp = self.compute_exp(x) + self.pows_till_i(x, to-i)
            x,i = self.binsearch(1,1<<64,frm)
            exp -= self.compute_exp(x) + self.pows_till_i(x,frm-i-1)

            answ = 1
            base = 2
            while exp > 0:
                answ *= base if (exp%2) == 1 else 1
                answ = answ % mod
                base = (base**2)%mod
                exp = exp >> 1
            answer += [answ % mod]

        return answer
16800