UTS Open '21 P7 - April Fools

View as PDF

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

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.

All are pairwise distinct.

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