Count Good Subarrays :
Difficulty Level : Medium
Submissions : 272
Asked In :
Marks :15
: 3 | : 0
A good array is an array if you can reduce it to an array of zeroes by using the following move :
- Select any two elements and subtract $$$2^i$$$ from each element if their $$$bitwise-AND$$$ contains $$$1$$$ at $$$i-th$$$ bit.
You are given an array $$$A$$$ containing $$$n$$$ non negative integers. Now you need to find the number of good subarrays in array $$$A$$$. Since the number can be very large print the answer modulo $$$10^9 + 7$$$.
The first line of input contains an integer $$$t \hspace{2pt} (1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first line of each testcase contains an integer $$$n \hspace{2pt} (1 \le n \le 10^5)$$$ — the number of elements in the array $$$A$$$.
The second line of each testcase contains $$$n$$$ space separated integers $$$a_0, a_1, ... a_n$$$ $$$(0 \le a_i \le 10^9)$$$ — the elements of array $$$A$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$10^5.$$$
For each testcase, print a single integer — the number of good subarrays of array $$$A$$$ modulo $$$10^9 + 7$$$.
141 0 3 2
2
In sample testcase 1,
- subarray $$$[0]$$$ is already good.
- subarray $$$[1,0,3,2]$$$ can be made a good array, by subtracting $$$2$$$, from index $$$3$$$ and $$$4$$$ since their bitwise AND is $$$2$$$. and $$$1$$$ can be subtracted from index $$$1$$$ and index $$$3$$$ since their $$$bitwise-AND$$$ is $$$1$$$.
