D. OR MEX
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a permutation $$$p_1, p_2, \dots, p_n$$$ of length $$$n$$$. The elements of $$$p$$$ are a permutation of the integers $$$0, 1, \dots, n-1$$$.

For a non-empty array $$$a = [a_1, a_2, \dots, a_m]$$$, we define the function $$$f(a)$$$ as: $$$$$$ f(a) = (a_1 | a_2 | \dots | a_m) \times \text{MEX}(\{a_1, a_2, \dots, a_m\}) $$$$$$

Your task is to calculate the sum of $$$f$$$ applied to all contiguous subarrays of $$$p$$$. You need to compute the value $$$S$$$, modulo $$$10^9 + 7$$$: $$$$$$ S = \sum_{l=1}^n \sum_{r=l}^n f([p_l, p_{l+1}, \dots, p_r]) $$$$$$

Here, $$$(a_1 | a_2 | \dots | a_m)$$$ represents the result of applying the bitwise-OR operation to all elements $$$a_1, a_2, \dots, a_m$$$. For example, if $$$a = [1, 2, 4]$$$, the bitwise OR is $$$1 | 2 | 4 = 7$$$.

The function $$$\textbf{MEX}(S)$$$ for a set of non-negative integers $$$S$$$ is defined as the smallest non-negative integer that is not present in the set $$$S$$$. For example, $$$\text{MEX}(\{0, 1, 3\}) = 2$$$ and $$$\text{MEX}(\{1, 2\}) = 0$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^6$$$), the number of test cases.

Then $$$T$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the length of the permutation.

The second line of each test case contains $$$n$$$ distinct integers $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \le n-1$$$), representing the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer representing the calculated sum $$$S$$$, modulo $$$10^9 + 7$$$.

Example
Input
2
2
0 1
3
1 2 0
Output
2
11