//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define endl '\n'
const int N=1010;
const ll mod=1000000007;
int S[7][7][N][N];
int a[N];
ll pw[N*N];
void solve(){
pw[0]=1ll;
for (int i=1;i<N*N;i++){
pw[i]=(pw[i-1]*2ll)%mod;
}
int n;cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
}
int q;cin>>q;
for (int i=1;i<=q;i++){
int l,r,x;cin>>l>>r>>x;
for (int j=0;j<7;j++){
for (int t=0;t<7;t++){
if ((x&(1<<j)) && (x&(1<<t))){
S[j][t][l][r]++;
}
}
}
}
for (int x=0;x<7;x++){
for (int y=0;y<7;y++){
for (int i=1;i<=n;++i){
for (int j=1;j<=n;j++) S[x][y][i][j]+=S[x][y][i][j-1];
for (int j=1;j<=n;j++) S[x][y][i][j]+=S[x][y][i-1][j];
}
}
}
ll res=0ll;
for (int i=1;i<=n;i++){
for (int j=i;j<=n;j++){
ll mult=i*(n-j+1);
if (i<j) mult*=2;
for (int x=0;x<7;x++){
for (int y=0;y<7;y++){
int cnt=S[x][y][j][j]-S[x][y][i-1][j]-S[x][y][j][i-1]+S[x][y][i-1][i-1];
int cnt_x=S[x][x][j][j]-S[x][x][i-1][j]-S[x][x][j][i-1]+S[x][x][i-1][i-1];
int cnt_y=S[y][y][j][j]-S[y][y][i-1][j]-S[y][y][j][i-1]+S[y][y][i-1][i-1];
cnt_x-=cnt;
cnt_y-=cnt;
int SS=(cnt>0)+(cnt_x>0)+(cnt_y>0);
// if (i==1 && j==1 && x==0 && y==1){
// cout<<"OK "<<mult<<" "<<SS<<endl;
// }
// if (i==1 && j==1 && x==0 && y==1){
// cout<<"OK "<<mult<<" "<<SS<<endl;
// }
// if (i==1 && j==1 && x==0 && y==1){
// cout<<"OK "<<mult<<" "<<SS<<endl;
// }
// if (i==1 && j==1 && x==0 && y==1){
// cout<<"OK "<<mult<<" "<<SS<<endl;
// }
if (SS>=2){
res+=pw[q-2+x+y]*mult;
res%=mod;
} else if ((a[i]&(1<<x)) && (a[j]&(1<<y))){
// cout<<i<<" "<<j<<" "<<x<<" "<<y<<endl;
// cout<<mult<<endl;
res+=pw[q-SS+x+y]*mult;
res%=mod;
} else if ((a[i]&(1<<x)) && (a[j]&(1<<y))==0 && cnt_y){
res+=pw[q-SS+x+y]*mult;
res%=mod;
} else if ((a[i]&(1<<x))==0 && (a[j]&(1<<y)) && cnt_x){
res+=pw[q-SS+x+y]*mult;
res%=mod;
} else if ((a[i]&(1<<x))==0 && (a[j]&(1<<y))==0 && cnt){
res+=pw[q-SS+x+y]*mult;
res%=mod;
}
}
}
}
}
cout<<res<<endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt=1;
while (tt--){
solve();
}
return 0;
}
/*
2
1 3
1
1 2 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8940 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9452 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
10476 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8940 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9452 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
10476 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
27904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1533 ms |
202220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8940 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9452 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
10476 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8940 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9452 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
10476 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8940 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9452 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
10476 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
