样例可过但是满江红

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m;
int ln;
int fa[N][20];
int find(int x,int y){
	if(fa[x][y]==x)return x;
	fa[x][y]=find(fa[x][y],y);
	return fa[x][y];
}
bool vis[N];
signed main(){
	cin>>n>>m;
	ln=(int)log(n);
	for(int i=1;i<=n;i++){
		for(int j=0;j<=ln;j++){
			fa[i][j]=i;
		}
	} 
	while(m--){
		int l1,r1,l2,r2;
		cin>>l1>>r1>>l2>>r2;
		int d=r1-l1+1;
		for(int i=ln;i>=0;i--){
			if((1<<i)<=d){
				if(find(l1,i)!=find(l2,i)){
					fa[find(l1,i)][i]=find(l2,i);
				}
				l1+=(1<<i);l2+=(1<<i);
				d=d-(1<<i);
			}
		}
	}
	int mid,r;
	for(int j=ln;j>=1;j--){
		for(int i=1;i+(1<<j)-1<=n;i++){
			mid=i+(1<<(j-1)),r=1+(1<<j)-1;//第一个和第二个终点
			if(find(i,j)!=i){
				fa[find(i,j-1)][j-1]=find(find(i,j),j-1);
				fa[find(mid,j-1)][j-1]=find(find(i,j)+(1<<(j-1)),j-1);
			} 
		}
	}
	int ans=0,ans2=9;
	for(int i=1;i<=n;i++){
		//cout<<fa[i][0]<<' ';
		if(vis[fa[i][0]]==0){
			vis[fa[i][0]]=1;
			ans++;
		}
	}
	for(int i=1;i<ans;i++)ans2=(ans2*10)%1000000007;
	cout<<ans2;
	return 0;
}