题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
char IO;
int rd(){
int s=0;
while(!isdigit(IO=getchar()));
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return s;
}

const int N=2e4+10,P=1e9+7,I2=(P+1)/2,I3=(P+1)/3,U=1<<30;

int n,m,k;
int L[N],R[N];
int Check(){
for(int i=k;i;i>>=1) if(~i&1) return 0;
return 1;
}
int D3(int n){ return 1lln(n-1)/2%P*(n-2)%PI3%P; }
int D2(int n){ return 1lln*(n-1)/2%P; }

const int M=N*60;
int s[M],ls[M],rs[M],t[M],cnt,rt;
void Ins(int &p,int l,int r,int ql,int qr){
if(!p) p=++cnt;
s[p]+=min(qr,r)-max(ql,l)+1;
if(ql<=l && r<=qr) { t[p]=1; return; }
int mid=(l+r)>>1;
if(ql<=mid) Ins(ls[p],l,mid,ql,qr);
if(qr>mid) Ins(rs[p],mid+1,r,ql,qr);
}

int ans;
int Up(int k){ return 1<<(32-__builtin_clz(k)); }
typedef vector <Pii> V;
V Union(const V &A,const V &B){
int p1=0,p2=0,s1=A.size(),s2=B.size();
V R;
while(p1<s1 || p2<s2) {
if(p1<s1 && (p2s2||A[p1]<B[p2])) {
if(R.size() && R.back().firstA[p1].first) R.back().second+=A[p1].second;
else R.pb(A[p1]);
p1++;
} else {
if(R.size() && R.back().firstB[p2].first) R.back().second+=B[p2].second;
else R.pb(B[p2]);
p2++;
}
}
return R;
}
V Calc(int a,int b,int L,int k,int f1,int f2){
f1|=t[a],f2|=t[b];
V Res;
if(!f1 && !a) return Res;
if(f2) return Res.pb(mp(k+1,f1?L:s[a])),Res;
if(!b) return Res.pb(mp(0,f1?L:s[a])),Res;
int m=Up(k);
if(L>m) return Union(Calc(ls[a],ls[b],L/2,k,f1,f2),Calc(rs[a],rs[b],L/2,k,f1,f2));
k-=m/2;
V A=Calc(ls[a],rs[b],L/2,k,f1,f2);
for(auto &i:A) i.first+=f2?L/2:s[ls[b]];
V B=Calc(rs[a],ls[b],L/2,k,f1,f2);
for(auto &i:B) i.first+=f2?L/2:s[rs[b]];
return Union(A,B);
}
int cm;
void Solve(int p,int L){
if(!p) return;
if(t[p]) { cm+=L/m; return; }
if(Lm) {
ans=(ans+D3(s[ls[p]]))%P,ans=(ans+D3(s[rs[p]]))%P;
V A=Calc(ls[p],rs[p],m/2,k-m/2,0,0);
V B=Calc(rs[p],ls[p],m/2,k-m/2,0,0);
for(auto i:A) ans=(ans+1llD2(i.first)i.second)%P;
for(auto i:B) ans=(ans+1llD2(i.first)i.second)%P;
return;
}
Solve(ls[p],L/2),Solve(rs[p],L/2);
}
int main(){
n=rd(),k=rd();
rep(i,1,n) { int l=rd(),r=rd(); Ins(rt,0,U-1,l,r); }
m=Up(k),Solve(rt,U);
int t=(2llD3(m/2)+1llD2(k-m/2+1)m)%P;
ans=(ans+1llcm*t)%P;
printf("%d\n",ans);
}