전부 켜는 부분집합

첫 줄에 수의 개수 n (1 이상 16 이하) 이 주어집니다. 둘째 줄에 n개의 정수가 주어집니다. 각 수는 1 이상 1000000 이하입니다.

크기가 1 이상인 부분집합 중, 원소들을 모두 OR 한 값이 전체 n개를 모두 OR 한 값과 같아지는 것이 몇 개인지 출력하세요.

예시

입력

3
1 2 3

출력

5