前置芝士

1.nim博弈/SG函数
2.FWT

做法

经典的nim博弈是n个数，每次可取任意数，SG[n]=n,本题中只能取魔法数字和 的数，所以得自己求一下SG函数。

(mex运算表示求不属于该集合的最小非负整数)

暴力求解SG函数肯定会超时，考虑用bitset优化。
1.首先开一个bitset，第 i 位表示 i 是否属于可以取的数，然后筛出所有 miu[x]=1 的数，对于这些数和数据给出的魔法数字，在bitset的对应位置标上1。
2.再开231个（为什么是231呢，因为据出题人说，他用模拟退火跑了一天得出的最大SG值为 230 ）100001 位的bitset，第 i 个bitset的第 j 位，表示 j 是否有值为 i 的出边。
3.从小到大求每个SG函数的值，每求出一个SG[x]，就要更新对应的bitset，这里我们用 b[SG[x]]|=opt<<x 就可以很方便的完成更新。
预处理复杂度是 100000 * 100000 / 64

求出SG函数后，答案就是 中大于0的个数，可以用FWT求。

由于题目中n达到了1e6，直接对每个位置都FWT一遍会超时，因为 ,所以我们进行预处理，对每个前缀FWT，这样每个位置FWT后的结果就可以直接由前缀和相减得到。
最后答案可以用总数减去等于0的个数。
对前缀FWT的复杂度是 100000 * 256 * 8 ，求解的复杂度是O(256n)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<class T>
inline void read(T &x){
x=0; int sign=1; char c;
do{c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c));
do{x=x*10+c-'0',c=getchar();}while(isdigit(c));
x*=sign;
}
const int N = 100005,mod=1e9+7,inv2=500000004;
int miu[N],sg[N],sum[N][260],M;
bool v[N];
vector<int> prime;
bitset<N> b[260],opt;
void prework(){
    miu[1]=1;             //线性筛求莫比乌斯函数
    for(int i=2;i<=100000;++i){
        if(!v[i]) prime.push_back(i),miu[i]=-1;
        for(int j:prime){
            if(j>100000/i) break;
            v[i*j]=1;
            if(i%j) miu[i*j]=-miu[i];
            else{
                miu[i*j]=0;
                break;
            }
        }
    }
    for(int i=1;i<=100000;++i) if(miu[i]==1) opt[i]=1;

        b[0]=opt;          //求SG函数
    for(int i=1;i<=100000;++i){
        while(b[sg[i]][i]) ++sg[i];
        M=max(M,sg[i]);
        b[sg[i]]|=opt<<i;
    }

    int T=1;       //对每个SG函数的值求前缀和
    while(T<M+1) T<<=1;
    M=T;
    for(int i=1;i<=100000;++i){
        for(int j=0;j<M;++j) sum[i][j]=sum[i-1][j];
        ++sum[i][sg[i]];
    }
}
void FWT_XOR(int *a){          //FWT
    for(int k=1,len=1;len<M;++k,len<<=1)
    for(int i=0;i<M;i+=1<<k)
    for(int j=i;j<i+len;++j){
        int u=a[j],v=a[j+len];
        a[j]=u+v,a[j+len]=u-v;
        if(a[j]>mod) a[j]-=mod;
        if(a[j+len]<0) a[j+len]+=mod; 
    }
}
void IFWT_XOR(int *a){        
    for(int k=1,len=1;len<M;++k,len<<=1)
    for(int i=0;i<M;i+=1<<k)
    for(int j=i;j<i+len;++j)
    a[j]=(a[j]+a[j+len])%mod,
    a[j+len]=(a[j]-a[j+len]-a[j+len])%mod,
    a[j]=1LL*a[j]*inv2%mod,a[j+len]=1LL*a[j+len]*inv2%mod;
}
int n,m,t,l[N*10],r[N*10],B[260];
int main(){
    read(n),read(m);
    for(int i=1;i<=n;++i) read(l[i]),read(r[i]);
    for(int i=1;i<=m;++i) read(t),opt[t]=1;
    prework();
    ll ans=1;
    for(int i=1;i<=100000;++i) FWT_XOR(sum[i]);  // 预处理每个前缀
    for(int i=0;i<M;++i) B[i]=1;
    for(int i=1;i<=n;++i) {
        ans=ans*(r[i]-l[i]+1)%mod;
        for(int j=0;j<M;++j) B[j]=1LL*B[j]*(sum[r[i]][j]-sum[l[i]-1][j])%mod;
    }
    IFWT_XOR(B);    //逆变换，得到答案
    printf("%lld",(ans+mod-B[0])%mod);
return 0;
}