Inaba is running her own competitive programming website called UTSOJ (UTSOJ: The Splendid Online Judge). As an April Fool's joke, she is planning to give everyone's rating graph a downwards trend! However, she does not want to anger her users too much, so she decides that their rating graph must be stably decreasing. She defines a stably decreasing rating graph as a rating graph where each subsequent rating is either lower than the previous rating, or the left-most bit of the current rating is one position off from the left-most bit of the previous rating. Formally, define ~\text{MSB}(x)~ as the index of the most significant bit in the binary representation of ~x~. Given a ~1~-indexed array ~A~ with ~N~ elements, a permutation of ~A~ is defined as stably decreasing if for all ~i > 1~, ~A_{i-1} > A_i~ or ~|\text{MSB}(A_{i-1}) - \text{MSB}(A_i)| = 1~. Since Inaba wants to know how creative she can get, please help her find the number of different stably decreasing permutations of a given array ~A~. Two permutations are considered different if at any index ~i~, the value at index ~i~ of the two permutations are different.

Constraints

For this problem, you will NOT be required to pass the sample cases in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

~1 \le N \le 500~

~1 \le A_i \le 10^9~

All ~A_i~ are pairwise distinct.

Subtask 1 [10%]

~1 \le N \le 10~

Subtask 2 [30%]

~1 \le N \le 50~

Subtask 3 [20%]

~1 \le N \le 100~

Subtask 4 [40%]

No additional constraints.

Input Specification

The first line contains an integer ~N~, the length of ~A~.

The next line contains ~N~ integers ~A_i~ ~(1 \le i \le N)~, representing the elements of array ~A~.

Output Specification

Output one integer, representing the number of different stably decreasing permutations of ~A~. Since this value may be large, output it modulo ~10^9 + 7~.

Sample Input 1

3
1 3 2

Sample Output 1

4

Explanation for Sample 1

The four stably decreasing permutations are:

• ~[1, 3, 2]~ - valid because ~|\text{MSB}(A_1) - \text{MSB}(A_2)| = 1~ and ~A_2 > A_3~.
• ~[2, 1, 3]~ - valid because ~A_1 > A_2~ and ~|\text{MSB}(A_2) - \text{MSB}(A_3)| = 1~.
• ~[3, 1, 2]~ - valid because ~A_1 > A_2~ and ~|\text{MSB}(A_2) - \text{MSB}(A_3)| = 1~.
• ~[3, 2, 1]~ - valid because ~A_1 > A_2~ and ~A_2 > A_3~.

And the two other permutations are:

• ~[1, 2, 3]~ - invalid because ~A_2 < A_3~ and ~|\text{MSB}(A_2) - \text{MSB}(A_3)| \ne 1~.
• ~[2, 3, 1]~ - invalid because ~A_1 < A_2~ and ~|\text{MSB}(A_1) - \text{MSB}(A_2)| \ne 1~.

Sample Input 2

19
1133 1010 1043 1289 1463 1587 1664 1769 1834 1915 1897 1951 1978 2014 2111 2133 2206 2267 2298

Sample Output 2

994855688

Explanation for Sample 2

Be sure to output your answer modulo ~10^9 + 7~.