#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define lc(x) (x<<1) #define rc(x) (x<<1|1) #define p1(x) x.first #define p2(x) x.second #define endl "\n" int n; int a[200030]; const int M=998244353; inline int lg(int x){ int res=0; while(x)res++,x>>=1; return res; } int f[1030][1030]; const int IV2=(M+1)/2; inline int adt(int x,int y){ if(x+y>=M)return x+y-M; return x+y; } inline int mns(int x,int y){ if(x>=y)return x-y; return x-y+M; } inline int ppc(int x){ return __builtin_popcount(x); } inline int gt(int S,int x){ return (S>>(x-1))&1; } inline int un(int x){ return 1ll<<(x-1); } int N; inline int ccs(int c,int S){ c++; int res=N^S; // cout<<N<<" "<<S<<" "<<res<<" "; for(int i=1;i<=n;i++) if(gt(S,i)&&gt(a[i],c))res|=un(i); return res; } inline int aft(int c,int S,int p){ c++; int res=S; for(int i=1;i<=n;i++) if(gt(S,i)&&gt(p,i)!=gt(a[i],c)) res^=un(i); return res; } int F[40][1<<17]; signed main() { // freopen("crystal.in","r",stdin); // freopen("crystal.out","w",stdout); ios::sync_with_stdio(0); cin>>n; int mx=0,ct=0; for(int i=1;i<=n;i++){ cin>>a[i]; int w=lg(a[i]); if(w==mx)ct++; else if(w>mx)mx=w,ct=1; } // cout<<mx<<" "<<ct<<endl; if(ct==1){ sort(a+1,a+n+1); int res=1; for(int i=1;i<n;i++) res=res*(a[i]+1)%M; cout<<res<<endl; } else if(mx<=10){ for(int i=0;i<1024;i++) for(int j=0;j<=i;j++) f[i][j]=1; f[1024][0]=1; for(int k=0;k<=1024;k++) for(int t=1;t<1024;t<<=1) for(int i=0;i<1024;i+=2*t) for(int j=i;j<i+t;j++){ int a=f[k][j],b=f[k][j+t]; f[k][j]=adt(a,b); f[k][j+t]=mns(a,b); } // for(int i=0;i<16;i++,cout<<endl) // for(int j=0;j<1024;j++) // cout<<f[i][j]<<" "; for(int i=1;i<=n;i++) for(int j=0;j<1024;j++) f[1024][j]=f[1024][j]*f[a[i]][j]%M; int k=1024; for(int t=1;t<1024;t<<=1) for(int i=0;i<1024;i+=2*t) for(int j=i;j<i+t;j++){ int a=f[k][j],b=f[k][j+t]; f[k][j]=adt(a,b)*IV2%M; f[k][j+t]=mns(a,b)*IV2%M; } cout<<f[k][0]<<endl; // for(int i=0;i<64;i++) // cout<<f[k][i]<<" "; } else if(n<=16){ N=(1<<n)-1; F[32][N]=1; for(int c=31;c>=0;c--){ for(int S=0;S<=N;S++)if(F[c+1][S]){ // cout<<c<<" "<<S<<endl; int E=ccs(c,S); // cout<<E<<endl; // cout.flush(); for(int SE=E;;SE=(SE-1)&E){ if(ppc(SE)%2)continue; // cout<<SE<<"x";cout.flush(); int T=aft(c,S,SE); // cout<<T<<" ";cout.flush(); F[c][T]=adt(F[c][T],F[c+1][S]); if(SE==0)break; } // cout<<endl; } } int res=0; for(int i=0;i<=N;i++) res=adt(res,F[0][i]); cout<<res<<endl; } cout.flush(); return 0; } /* 8 19 20 23 25 37 38 39 40 */