给出一个\(n\)个数的集合，定义任意一个子集S的价值为\(|S|\cdot max\cdot min\cdot(\bigoplus_{x\in S}a_x)\)
显然可以先将\(\{a_i\}\)进行由小到大的排序。
先考虑只有一个数字的情况答案为\(\sum a_i^3\)
考虑枚举\(i,j,(j<i)\) 那么\(max\)和\(min\)就有了
之后考虑\(i\)和\(j\)之间选取一些数字。
容易发现这个异或并不好做可以进行拆位，每次我们只考虑求出二进制下第\(k\)位的答案。
如果不考虑\(|S|\)的贡献，那么我们只需要求出\(i-j\)之间有多少种方案使得异或出来第\(k\)位为\(1\)，此时可设\(g_{i,j}\)表示到了第\(i\)位选出的数的使得异或成第\(k\)位为\(0/1\)的和。
接下来考虑\(|S|\)的贡献容易发现如果对于当前的数字是不选的那么\(g_{i,j}\)不变，如果选了当前这个数字我们只需要再加上一遍\(g_{i,j}\)即可满足\(|S|\)的限制。
这个地方使用很妙的方法解决了\(|S|\)的贡献。
const ll MAXN=1000010;
ll n, m;
ll a[MAXN];
ll f[MAXN][2],g[MAXN][2];
ll ans=0;
inline void solve(ll x)
{
rep(1,n,i)
{
ll op=a[i]>>x;
op&=1;
rep(0,1,j)f[i][j]=f[i-1][j],g[i][j]=g[i-1][j];
rep(0,1,j)
{
f[i][j]=((f[i][j]+f[i-1][j^op])%mod+g[i-1][j^op])%mod;
g[i][j]=(g[i][j]+g[i-1][j^op])%mod;
}
f[i][op]=((ll)f[i][op]+a[i])%mod;
g[i][op]=((ll)g[i][op]+a[i])%mod;
ans=(ans+(ll)(f[i-1][op^1]+g[i-1][op^1])%mod*a[i]%mod*(1<<x))%mod;
}
}
signed main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
sc(n);
rep(1,n,i)sc(a[i]);
sort(a+1,a+1+n);
//cout<<(1<<30)<<endl;
rep(1,n,i)
{
//a[i]%=mod;
ans=(ans+(ll)a[i]*a[i]%mod*a[i])%mod;
}
rep(0,30,i)solve(i);
put(ans);
return 0;
}