// Author: Aquizahv #include <bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5 + 5, W = 50, w = 40; const ll all = (1ll << 40) - 1; int n; ll a[W], v[W], unit[W], filt[W], f[(1 << 20) + 5], ans; bool vis[W]; inline ll read() { ll x = 0; char ch = getchar(); while (ch < '0' || ch > '9') { ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1ll) + (x << 3ll) + (ch ^ 48); ch = getchar(); } return x; } void print(ll mask) { for (int k = 0; k < 40; k++) putchar(((mask >> k) & 1) + '0'); putchar('\n'); } void dfs(int i, ll mask) { if (i >= 40) { // print(mask); ans += f[mask & ((1 << 20) - 1)]; // cout << ans << endl; return; } dfs(i + 1, mask); if (vis[i] && (mask & (1ll << i))) { // cout << "choose: " << i << endl; dfs(i + 1, mask & filt[i]); } } int main() { n = read(); int gca = all; for (int i = 1; i <= n; i++) { a[i] = read(); gca &= a[i]; } for (int k = 0; k < 40; k++) unit[k] = filt[k] = all; for (int i = 1; i <= n; i++) { a[i] ^= gca; for (int k = 0; k < 40; k++) if ((a[i] >> k) & 1) { vis[k] = true; unit[k] &= a[i]; } } // if i include j, then cannot choose both // && the ks which doesnt appear (extra check) (included) for (int i = 0; i < 40; i++) for (int j = 0; j < 40; j++) if ((i != j || !vis[i]) && ((unit[i] & unit[j]) == unit[i] || (unit[i] & unit[j]) == unit[j])) { filt[i] &= all ^ (1ll << j); filt[j] &= all ^ (1ll << i); } // for (int k = 0; k < 3; k++) // print(filt[k]); // for (int k = 0; k < 40; k++) // print(filt[k]); // FMT 20~39 for (int mask = 0; mask < (1 << 20); mask++) { bool flag = true; for (int k = 0; k < 20; k++) if ((mask & (1 << k)) && (mask & filt[k]) != mask) { flag = false; break; } if (!flag) continue; f[mask]++; } // for (int mask = 0; mask < (1 << 20); mask++) // cout << f[mask] << ' ', print(mask); for (int k = 0; k < 20; k++) for (int mask = 0; mask < (1 << 20); mask++) if (mask & (1 << k)) f[mask] += f[mask ^ (1 << k)]; // for (int mask = 0; mask < (1 << 20); mask++) // cout << f[mask] << ' ', print(mask); // DFS 0~19 dfs(20, all); cout << ans << endl; return 0; }