D. RestORe
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Consider a sequence of non-negative integers from $$$L$$$ to $$$R$$$ inclusive. Split this sequence into $$$n$$$ non-empty segments and calculate the bitwise "OR" of all numbers in each segment. Denote the result for the $$$i$$$-th segment as $$$f_i$$$.

You need to solve the inverse problem: given $$$f_1, f_2, \ldots, f_n$$$, find the number of ways first to select $$$L$$$ and $$$R$$$, and then split all numbers from $$$L$$$ to $$$R$$$ into $$$n$$$ non-empty segments, such that the results of calculating the bitwise "OR" in each segment are equal to $$$f_1, f_2, \ldots, f_n$$$ respectively.

The bitwise "OR" of two non-negative integers is calculated as follows: Write down both arguments in binary, then the $$$i$$$-th bit of the result equals $$$1$$$ iff at least one argument has $$$1$$$ at that place. For example, $$$(17 \mathbin{|} 13) = (10001_2 \mathbin{|} 01101_2) = 11101_2 = 29$$$.

Input

The first line contains integer $$$n$$$ ($$$1 \le n \le 200\,000$$$). The second line contains $$$n$$$ integers $$$f_i$$$ ($$$0 \le f_i \lt 2^{60}$$$).

Output

Output a single integer — the number of ways to choose a sequence of consecutive integers and then split it into $$$n$$$ segments. Because the answer can be huge, print it modulo $$$1\,000\,000\,007$$$.

Scoring
SubtaskPointsConstraints
116$$$n = 1$$$
212$$$n \le 16$$$, $$$0 \le f_ilt; 16$$$
313$$$n \le 256$$$, $$$0 \le f_ilt; 256$$$
418$$$n \le 1024$$$, $$$0 \le f_ilt; 1024$$$
524$$$n \le 30\,000$$$, $$$0 \le f_ilt; 2^{30}$$$
617No additional constraints
Examples
Input
3
0 7 7
Output
4
Input
1
11
Output
6
Input
2
4 6
Output
0
Note

In the first example, there are four ways to split a sequence of consecutive integers into three parts such that their bitwise "OR"s are $$$0$$$, $$$7$$$ and $$$7$$$:

  • $$$[0], [1, 2, 3, 4, 5, 6], [7]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 \mathbin{|} 5 \mathbin{|} 6 = 7$$$; $$$7 = 7$$$
  • $$$[0], [1, 2, 3, 4, 5], [6, 7]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 \mathbin{|} 5 = 7$$$; $$$6 \mathbin{|} 7 = 7$$$
  • $$$[0], [1, 2, 3, 4], [5, 6, 7]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 = 7$$$; $$$5 \mathbin{|} 6 \mathbin{|} 7 = 7$$$
  • $$$[0], [1, 2, 3, 4], [5, 6]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 = 7$$$; $$$5 \mathbin{|} 6 = 7$$$