typedef long long LL ;
class FWT{
public:
void fwt(LL *a, int n){
for(int d = 1; d < n; d <<= 1){
for(int m = d<<1, i = 0; i < n; i += m){
for(int j = 0; j < d; j++){
LL x = a[i+j], y = a[i+j+d];
a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod;
//xor:a[i+j]=x+y,a[i+j+d]=(x-y+mod)%mod;
//and:a[i+j]=x+y;
//or:a[i+j+d]=x+y;
}
}
}
}
void ufwt(LL *a, int n){
for(int d = 1; d < n; d <<= 1){
for(int m = d<<1, i = 0; i < n; i += m){
for(int j = 0; j < d; j++){
LL x = a[i+j], y = a[i+j+d];
a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod;
//xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;
//and:a[i+j]=x-y;
//or:a[i+j+d]=y-x;
}
}
}
}
void work(LL *a, LL *b, int n){
fwt(a, n);
fwt(b, n);
for(int i = 0; i < n; i++) a[i] *= b[i];
ufwt(a, n);
}
}myfwt;