23042번 - AND와 OR

문제

당신에게 $N$개의 수가 주어집니다. 당신은 다음과 같은 작업을 하고 싶은 만큼 할 수 있습니다.

• 두 수를 고르고, 이 두 수를 두 수와 bitwise AND 및 bitwise OR가 모두 같은 두 음이 아닌 정수로 바꿉니다.

당신은 작업을 수행한 후 이 수들의 곱을 최소화하고 싶습니다. $N$개의 수의 최소화된 곱을 구하세요. 단, 이 곱이 매우 커질 수 있으니 10ドル^{9} + 7$로 나눈 나머지를 대신 출력합니다.

Bitwise AND와 bitwise OR에 대한 설명은 노트 란을 참고하세요.

입력

첫째 줄에 2ドル$ 이상 300ドル,000円$ 이하인 정수 $N$이 주어집니다.

둘째 줄에 $N$개의 양의 정수가 공백을 사이에 두고 주어집니다. 각 정수는 2ドル^{30}$보다 작습니다.

출력

첫째 줄에 최소화된 곱을 10ドル^{9} + 7$로 나눈 나머지를 출력합니다.

곱을 $\mathbf{10}^{\mathbf{9}} + \mathbf{7}$로 나눈 나머지를 최소화하는 것이 아님에 주의하세요.

제한

노트

Bitwise operation은 각 연산을 비트 단위로 시행하는 것입니다.

예를 들어, 28ドル$과 87ドル$을 bitwise AND 연산한다고 합시다. 먼저 28ドル$과 87ドル$을 비트가 잘 드러나도록 2진수로 바꾸겠습니다.

각 위치의 비트를 순서대로 AND해서 아래쪽에 적습니다. AND 연산의 경우 두 비트가 모두 1이어야만 결과가 1이고, 그렇지 않은 경우 0입니다.

마찬가지로 bitwise OR 연산을 시행할 수도 있습니다. OR 연산의 경우 두 비트가 모두 0이어야만 결과가 0이고, 그렇지 않은 경우 1입니다.