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 as the index of the most significant bit in the binary representation of . Given a -indexed array with elements, a permutation of is defined as stably decreasing if for all , or . 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 . Two permutations are considered different if at any index , the value at index 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:

All are pairwise distinct.

##### Subtask 1 [10%]

##### Subtask 2 [30%]

##### Subtask 3 [20%]

##### Subtask 4 [40%]

No further constraints.

#### Input Specification

The first line contains an integer , the length of .

The next line contains integers , representing the elements of array .

#### Output Specification

Output one integer, representing the number of different stably decreasing permutations of . Since this value may be large, output it modulo .

#### Sample Input 1

```
3
1 3 2
```

#### Sample Output 1

`4`

#### Explanation for Sample 1

The four stably decreasing permutations are:

- valid because and .

- valid because and .

- valid because and .

- valid because and .

And the two other permutations are:

- invalid because and .

- invalid because and .

#### 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 .

## Comments