思路太妙了啊……

容易才怪想到暴力，把区间内的每一个数字用并查集维护相等，然后设最后总共有$k$个并查集，那么答案就是$9*10^{k-1}$（因为第一位不能为0）

考虑倍增。我们设$f[i][j]$表示区间$[i,i+2^j-1]$，那么我们可以把原区间给拆成$log$个区间，然后维护这些区间的连通性

然而我们最后需要的是最底层的，也就是单独的节点的连通性。那么我们考虑如何将连通性向下传递。如果$f[i][j]$和$f[a][b]$连通，那么$f[i][j-1]$和$f[a][b-1]$一定连通（前半部分区间），$f[i+2^{j-1}][j-1]$和$f[a+2^{b-1}][b-1]$也一定连通

ps：连通性肯定都在同一层，所以实际上上面的$j$和$b$一般都是相等的

然后只要最后判最底层有几个并查集就好了

1 //minamoto 2 #include
     
       3 #include
      
        4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 int read(){ 8     #define num ch-'0' 9     char ch;bool flag=0;int res;10     while(!isdigit(ch=getc()))11     (ch=='-')&&(flag=true);12     for(res=num;isdigit(ch=getc());res=res*10+num);13     (flag)&&(res=-res);14     #undef num15     return res;16 }17 const int N=1e5+5,mod=1e9+7;18 int fa[N*17],id[N][21],num[N*17],log[N*17],bin[21],is[N*17],h[N*17],tot=0,cnt;19 int find(int x){
   return fa[x]==x?x:fa[x]=find(fa[x]);}20 void merge(int x,int y){21     x=find(x),y=find(y);22     if(h[x]
       
        h[y]) fa[y]=x;24     else fa[x]=y,++h[y];25 }26 int ksm(int b){27     int res=9,a=10;28     while(b){29         if(b&1) res=1ll*res*a%mod;30         a=1ll*a*a%mod,b>>=1;31     }32     return res;33 }34 int main(){35 //    freopen("testdata.in","r",stdin);36     int n=read(),m=read();37     bin[0]=1;for(int i=1;i<=16;++i) bin[i]=bin[i-1]<<1;38     for(int j=0;j<=16;++j) for(int i=1;i<=n;++i) id[i][j]=++tot,num[tot]=i,fa[tot]=tot,h[tot]=1;39     while(m--){40         int l1=read(),r1=read(),l2=read(),r2=read();41         for(int i=16;i>=0;--i) if(l1+bin[i]-1<=r1){42             merge(id[l1][i],id[l2][i]),l1+=bin[i],l2+=bin[i];43         }44     }45     for(int j=16;j;--j) for(int i=1;i+bin[j]-1<=n;++i){46         int x=find(id[i][j]),a=num[x];47         merge(id[a][j-1],id[i][j-1]),merge(id[a+bin[j-1]][j-1],id[i+bin[j-1]][j-1]);48     }49     for(int i=1;i<=n;++i)50     if(find(id[i][0])==id[i][0]) ++cnt;51     printf("%d\n",ksm(cnt-1));52     return 0;53 }